I have this peculiar problem with my WordPress (v2.2.1) installation on my website.
When I edit a page (and only a page, this does not apply to posts or attachments) and save it, the WordPress permalink structure gets messed up, resulting in a 404 Not Found showing up for all permalinks. Physical files are normally accessible.
First, I tried to reset my permalinks to the default value (?p=123 URL's). That resulted in the question whether I really wanted to change the permalink structure to an empty string, as can be seen here.
Second on the list: the .htaccess file. Since WordPress can't write to it, that couldn't be the problem. Nevertheless, I checked it anyway, and found it to be OK (works perfectly on my local server and also on my site when everything is as it should be).
So it had to do with WordPress itself. I took a look at the options table in WordPress's database, and found two interesting rows: permalink_structure and rewrite_rules. The first one is simply that what's been chosen in the Permalinks admin panel. The second is a lot of abracadabra that I assume WordPress uses to determine what page/post to show.
And that's exactly where I found the problem was. I used phpMyAdmin to paste the value from my local WordPress installation (which is a mirror of my website, but works just fine) into that row, and voila, things were back to normal.
So I assumed it was just a glitch and everything was OK again. Well, it was not. Next time I edited a page, boom, same problem. Fortunately I now know how to fix it, so in a matter of minutes things were working again.
Next step was to deactivate all plugins, revert to the default WordPress theme and try again. Same problem.
Then, I exported my site contents through the Export admin panel, dropped all the tables in WordPress's database, re-ran wp-install.php, imported my site contents then and reset all options to my needs. Problem persisted.
As a final and desperate step, I trashed all WordPress related files from the server except for wp-config.php, my theme and my plugins. Then I uploaded a freshly downloaded copy of WordPress back to the server and repeated all the steps above. No luck, problem still persists.
I'm out of ideas now, short of diving into the core of WordPress to figure out what goes wrong. But that step is a just a little too steep for me.
Right now, I avoid editing pages as much as possible, and when I have to, I just paste the rewrite_rules from my local WordPress installation directly into the database, but you'll understand that having to do that over and over again quickly gets pretty awkward.
So, if anyone can help me out with this one, it would be much appreciated.