As I said, that was what worked for me, and I'm looking for a more elegant solution. I am using WP2.0, but I'm a new user this week, so I don't know a great deal about it. I needed a quick fix, and this was the best I could do.
First, I would check to see if permalinks are in fact the problem. Go to the admin page, then Options >> Permalinks. Choose the default option (?p=123). Copy down your custom string first if you don't want to lose it. Now test your site. Are pages working? They were for me.
What moshu said (replace current .htaccess file with empty, writable one, then update permalinks) is probalby the way to go. This is actually what I tried before my host informed me that they'd 'upgraded' they're servers to IIS without telling me.
Moshu, do you know where in the WP code the permalinks are created? I may be able to adapt the code to produce ISAPI_rewrite rules in an httpd.ini file. I'd be happy to host such a modification on my site. (I'm guessing that WP currently only does mod_rewrite in .htaccess).