Gandalf’s reference to the cats of Queen Berúthiel in Fellowship is possibly one of the most cryptic broken references in the entire Lord of the Rings. The story seems to be non-existent – there is no chapter on it in the History of Middle-earth series, or even in Unfinished Tales. However, it does exist; it’s just very hard to find, since it’s a footnote to the essay on the Istari (footnote 7) in UT.
Berúthiel was the wife of the first Gondorian ship-king, Tarannon; unfortunately for her, she hated the sea. As a result, the marriage was unhappy, and they became the first royal couple of Gondor never to have children. Instead, the queen devoted herself to her cats: nine black ones and one white, with whom she could talk or alternatively see their memories. She used them to spy on her people, and everyone was afraid of them; they would curse and avoid them.
Finally Tarannon got tired of her antics and removed her name from the Book of Kings and exiled her to a ship with her cats, which was driven from Gondor by a north wind.
I love this story because I harbour a powerful dislike of felines and enjoy the depiction of Berúthiel’s as evil. 😛