Hello eschwartz, thanks for your reply.
Not sure how "Kindle will remember" my books once I've deleted them, what exactly do you mean? Unless you mean the collections themselves as categories, which of course is not what I'm after (I only have a handful of easily remembered collections I can recreate, it's the multitutde of books that's the problem)...
As for your second suggestion, yes, I did delete and re-add the new books that pose the problem, as I mentioned in the OP, but the problem persists
Hence kovidgoyal's suggestion that I deleted all of my books.