I've read a boatload of different posts here with Permalink configuration troubles, primarily when WordPress is hosted in a Windows IIS environment. The php.ini hack that is suggested is not something many webhost providers (including mine) will do, and that's the only option I've seen for enabling permalinks on Win.
This is just a feature that is Apache-only on Windows. Just say it, and preferably disable the feature altogether in the control panel. Or, come up with a way to restructure the permalink feature (maybe use a valid querystring approach for access?) so it will work.