I also get a similar problem on IIS6 with wordpress 2.7 installed to the root of my domain.
I’ve changed permalinks to /index.php/%category%/%postname%/
When I do this, http://www.mydomain.com/ is inaccessible, however http://www.mydomain.com/index.php is accessible. Also, all posts are accessible as http://www.mydomain.com/index.php/categoryname/post/
It’s just the root domain entry page that gives a 404 error in my logs looking for /Index.php, throws a 404 error.
Any ideas?
UPDATE: I managed to fix this by changing the site hosting from using php-cgi to phpisapi. I don’t think it will affect anything. – sorry to hijack the OP.