I believe it's called nominative use. It's actually a hot topic right now, from what I understand. I think there's a very recent case on this topic.
Remember, a trademark doesn't give you the right to exclude others from ever uttering your trademark without your permission. It only reserves your trademark for use in describing your goods and/or services.
What that means is that I should be able to say that my new Jimbo Cola tastes better than Coca Cola -- since I'm using the "Coca Cola" trademark to describe the Coca Cola product. That's what the trademark is for -- an identifier for the purpose of identifying a source of goods and/or services. Without trademarks, I'd have to say something like "my cola beverage that is made by me, Jimbo, is better than that other cola beverage made by the very large international corporation headquartered in Atlanta, Georgia."
Now, trademark owners don't always see nominative use as harmless, and so often sue to stop nominative use. They sometimes claim that the nominative use gives an impression of affiliation -- or just makes them look bad.
Now, to the specific point of the "not ..." trailer on ebay item title lines. I understand what you're saying about it not seeming completely proper, but I see it as similar to what amazon.com does -- if you like this, you might also like that. More like, others who looked at this bought that, or others who bought that, looked at this.
Paid listings for Yahoo! and google sometimes get in trouble for doing something similar. As an example, consider that Pepsi bids for high placement of their web site in response to searches for "coke" or "coca-cola". Or that they put "coke, cocacola, coca-cola, coca cola," etc. in their metatags so they come up when searching any of those terms. Google and, I think Yahoo! too, have been in court over those sorts of uses.
Frankly, I think trademarks serve their intended purpose when someone uses nominative use of another's trademark to make a product/service comparison. It's a very useful thing if you're into competition and relatively free markets.
Regards.