I just ran into an orphaned site. The site was listed in the stsadm enumsites as "The Web site that is referenced here is not in the configuration database". Attempting to create a new site with the same name (and afterwards removing it again) failed with the message "Site with that name already exists". Deleting it with stsadm was also useless.
A little "google-ing" gave me some links to the blog of Keith Richie, a MS employee. He posted two articles about orphaned sites and how to deal with them:
Part 1: http://blogs.msdn.com/krichie/archive/2005/10/25/484889.aspx
Part 2: http://blogs.msdn.com/krichie/archive/2005/10/31/487365.aspx
Worked like a charm!!