It sounds like some other program was interfering with your library while calibre was moving things around. e.g. a Dropboxed library if calibre and Dropbox are running at the same time, can end up with moved files being recreated in the old location, or "conflicted copy" duplicates.
Regardless, the solution is as you surmised.
Create a fresh calibre library, then use Add Books, the second option in the dropdown: "Add books from directories, including sub-directories (One book per directory, assumes every ebook file is the same book in a different format)"
It will import the metadata from the metadata.opf backups.
Once the library is safely recreated, you may have to remove duplicates, the Find Duplicates plugin can help you there -- and yes, of course it will delete them from the hard drive (and send it to the Recycle Bin).
