Something that I was reminded of at eBay live, when attending the Organic and Natural search engine optimization seminar, was to write all my descriptions in lists using the bullet form. Bold the first line which should match the auction title line as the robots and search engine spiders see that as important and relevant information. Since I have been doing that again, I find my auctions pull up more easily.
I have found the same problem as you when searching for auctions. The more eBay works on the search engine, it seems the worse or pickier it gets. That's just my thought on it. I don't know if it really is but it seems that way to me anyway.