When the revisions are gone, can you change the permalink or still not?
It sounds a bit like overkill to delete the whole thing. If WP thinks the permalink is already in use, it has to be somewhere, but where?!?
I’ve got this problem as well. I’ve tried the suggestions above, as well as the WPSuperCache plugin. An example: my about page URL is /about-4. I edit the page (via Dashboard), click on edit permalink, and remove the “-4”. Which seems to work, until I update the page–then it reverts back to the -4 URL. I’m running WP 2.9.2.