As stated in the title, my 404 template in WordPress does not show up every time a non-existent URL is accessed in my site. The page works perfectly in FireFox and Chrome, though. So I made a quick search and found that the solution is to add another header information in the page. So here's what to insert at the very start of 404.php.

<?php ob_start(); ?> <?php header("HTTP/1.1 404 Not Found"); ?>

For this, credit goes to wpcanada. http://wpcanada.ca/2008/03/20/ie-and-custom-error-pages/

This is also touched in weblogtoolscollection.com at http://weblogtoolscollection.com/archives/2004/07/31/gzip-compression-issue-in-wordpress-12-mingus/

Note: ob_start() is a PHP function Turn on output buffering... whatever that means. :D