Luckily one of my colleagues came across this problem before. Apparently on IE5 and IE6 if a 404 error is thrown and the error page is LESS THAN 512 bytes...IE will try to be smart and use it's OWN "friendly" error page! -.- Wait...this does happen on IE7 too...because I was using IE7!!! (And IE will be smart for any error codes I think...not just 404).
The resolution of this is very simple (yet lame), I increased the size of my error page using a comment block. Note, if the error page is a JSP file, you MUST USE HTML comment block to make this work. If you use JSP comment, IE will not recgonise it as increasing the size of the file.
For the official detail about this "feature":
http://support.microsoft.com/kb/294807