This is a known issue[citation needed] and unfortunately restoring to a new content database is the only workaround (I refuse to call it a solution since you now have a new problem). Once restored, you can't move the site back either; the error it returns is about how the site used to exist in the content database.

If you can, avoid deleting site collections you intend on restoring again later. Use the `-force` parameter with [Restore-SPSite][2] or the `-overwrite` parameter with [stsadm -o restore][1]


  [1]: http://technet.microsoft.com/en-us/library/cc288929%28v=office.12%29.aspx
  [2]: http://technet.microsoft.com/en-us/library/ff607788.aspx