I deleted the metadata file, and let calibre go for 45 minutes. It seems to have looked at each and every file on my Nexus, but eventually synced ok. After that, it took the usual minute or two to send over the latest 8 or 10 books.
Unfortunately... Someone went into my office yesterday and took my Nexus out of a zippered compartment in my briefcase. No pings at all from Lookout, nothing from Plan B either, so I'm guessing it's gone for good.