Pretty Permalinks Only Work with Long Slugs

Are you adding index.php to the permalink setting? That is generally not required. Permalinks info at the Codex.

On IIS7 you need to work with your web.config file and do not need the .htaccess file: Some good info on IIS7 and WordPress on my site.

Yes I am using index.php – pretty permalinks didn’t work at all without it and it doesn’t bother me having it there.

To use pretty permalinks with IIS7 and remove the index.php part, you need Rewrite Module from Microsoft. But I’m not sure this (third party?) ISAPI-Rewrite has anything to do with your problem.

I hope you are not on IIS6, because a properly set up IIS7 with fast-CGI and Wincache is about 100 times faster and more reliable for PHP apps on PHP 5.3.

Of course, in shared hosting environment, a host can turn off the PHP Fast CGI process selectively with a goal of charging customers more (errr…making sites run better)…