[ddouglass]

As long as you didn't delete the 5000, then they should still be there. Did you get any "duplicate bookid messages? Check on rebuild database window and make sure all of the directory paths listed are correct and includes all of them. Check the folders where your kma files are located and make sure the count is right.
There really shouldn't have been any message/requirement to rebuild the database after deleting those songs as that would automatically update the database. Maybe it said rebuild (print) the songbook?
Also, as Lonman said if you are referring to your original disks as "initial hard copy" then you are operating illegally. You are supposed to keep your originals as proof of your license to use the computer copies.