Ken, when you say, "if Backup Exec chokes and says it already exists" do you mean when it has knowledge of the tape, but doesn't have it in the catalog? If so, then logic would dictate that you can just catalog it, but sometimes as you say, it chokes (complains about not being able to write to the database IIRC).
In that case, you CAN do as you say, shutdown services, rename catalogs folder, restart services, but in practice I found that you then needed to not use storage media based catalogs.
Another method which someone else found, and I found easier, is to simply delete the tape from BE. Move it to retired media first, then delete it from BE. Then reinventory it, and catalog it. I found this less hassle, faster (as you use the media based catalog), and all your catalogs are in the same place then.FAQ item added http://www.backupexecfaq.com/faq/using/how-to-find-the-contents-of-a-tape.html