Essentially, the problem is a credentials issue. If you can distinguish "serious" buyers from the "scammers," then you're set. I've done a little freelancing on elance.com, and the way they handle this problem is that they charge a small amount to make bids. Of course, this is somewhat different since one is bidding for jobs and not items (receiving money, not giving it), but it's still not very helpful, since I doubt anyone would pay even a nominal fee to make bids for buying items. Craiglist's solution to this problem is to limit buyers and sellers to their respective local geographic areas, which turns out to be pretty effective, but can oftentimes constrain market opportunities (and of course, there's no built-in auctioning capabilities).

I remember one post on YC a while back was about generating post modernism essays in response to spam emails to the point where a spammer could not possibly sift through all of them in a reasonable amount of time (and the "English" nature of the essays would make them hard to distinguish from real responses). This would make spamming unprofitable. Perhaps this can somehow be generalized to problems like s(c|p)ammers on eBay.