Magic happens: A new category has been added to all of my 10 books. It is a category that I had previously used. I can neither delete the category, nor add it to any contacts. Changing the name of the category in one book changes the name across all books (this could actually be a useful feature).
When I add a new local book the category is not there. It is also not there when I drag a contact from a different book. But the very moment I add a new contact, then the mystery category appears.
The mystery category cannot be added to a new contact. But it disappears when I delete the new contact. Magic happens!