Re: You Sure?
The "owned by Elvis Presley" example you give doesn't seem likely to be a trademark issue. It's not trademark infringement to state, factually, that a collectible item you are selling was previously owned by a famous person.
The key word there is "factually." The more specific key word is, "provenance," i.e., you had damned well be able to prove that particular Cadillac WAS owned by Elvis himself.
That said: I suppose it's possible Elvis Presley's estate threatened to sue eBay, or some other venue, or sellers of Elvis collectibles, and perhaps prevailed in an unusual copyright or trademark ruling, which prohibited the use of Elvis Presley's name in certain commercial contexts, including perhaps sales of items formerly owned by Presley.
But I'd like to see a copy of an actual court judgment if so. I'd also appreciate it if you'd point me to the part of U.S. Trademark law that states one needs permission simply to state the history of an item one is selling.
What is much more likely is that at one time 99% of the Elvis Presley memorabilia being auctioned on eBay was counterfeit, meaning thousands of buyers were cheated, leading eBay to change its own policies in response. I haven't checked, but it's at least possible eBay might prohibit sales/auctions of items said to be associated with Elvis simply to prevent fraud.
It's even more likely sellers claiming their item was once owned by some guy in a sparkly suit who sang 'Hound Dog' are referring to their Uncle Murray who did Elvis imitations at family parties. Counterfeiting is common - muzzling of free and truthful speech by trademark law not so common, despite some admittedly insane court rulings that might lead one to believe we don't even own our own names.