I've got a duplicated permalink somewhere, so I can't name the new one like that. Normally, I simply check the other posts, categories, media, even on the thrash. But this time I can't find any content with that permalink. I took a look to the database, did some search, but really can't find. It's strange. Is there any way to do a deeper search, or maybe some plugin that helps you cleaning up duplicated permalinks?
This can be a real pain, I know firsthand. The obvious place (that I sometimes forget) is your Trash folder. If it's not there, I would suggest re-saving permalinks.
As a last resort, I'd do what you said... a bunch of searches of the database. One time a plugin had auto-generated a page, and after disabling and deleting the plugin, I found the bad URL in the transients (the autosave stuff that WP does).