This started after a restart. This happens with all of my downloaded items. I have tried redoing the delivery on a few books. Same message. I de-registered the device and then re-registered it. Same result.
It might be better to speak to Customer Service if you want a speedy answer. They may already know of a solution. It's not something that has ever happened to me.
The closest I came to this was when nearly all the books from 2010 to 2013 disappeared from my Paperwhite after an update. It was something Amazon had to sort out with a further update.