[Dr. Drib]

Try this, if you haven't:

Delete the book FROM THE COLLECTION.

Ok, you now have the book still on the Kindle.

Now delete the book FROM THE KINDLE.

Let me know what happened, please.

---------------------------------------------
If the above didn't work, try this:
If the book is not on the Kindle, as you state, then ADD it to the Kindle using calibre. Now check to see where it's at: Is it in the Collection? Or outside of a Collection?

If it's in the Collection, delete it from the Collection (on your Kindle). Now delete the book from the Kindle itself, using calibre.

When deleting and/or adding the same title, I always disconnect my Kindle from my PC, in order to get the Kindle to refresh itself. Then I hook it back up and will go to the next step.