I haven't had the problem (yet) and 99% of my books are used but a good many have "New" in the title.

Harley, eBay seems to observe punctuation marks in search.

Maybe the bots will be confused by something like "Used" or *Used*