Here is the solution that worked for me (my host is running IIS 6 servers)
Go to this site http://www.nathanm.com/wordpress-plugins/ and download his plugin “WordPress Remove Index.php from Permalinks in IIS Plugin.”
Run it and install it into the plugins directory. Before activating it, go to the control panel that your host offers and set up your 404 error page to the relative root path of your blog. For instance, if your blog is installed in a subfolder on your domain, simply direct the 404 error page to that subfolder . . . e.g., /subfolder/.
Activate the plugin and voila!
NathanM has directions at the link I supplied as well.
Worked for me when nothing else would!
