This is a known issue[citation needed] and unfortunately restoring to a new content database is the only workaround (I wouldn't even 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 or the -overwrite parameter with stsadm -o restore

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 or the -overwrite parameter with stsadm -o restore