I think ebay isn't all that bad if you know what you're doing. The power sellers from Hong Kong are pretty much 100% safe. They get tons of feedback that you can easily check and see what people from the UK, US, and AU think about their games. if you're worried about bootleg games, just check for feedback on the specific game that you're buying (these sellers always sell more than one of the game). I bought Mario Kart DS from a power seller in hong kong and the game is 100% legitimate. It came in its package, shrink wrapped and everything. Brand new game, nothing wrong with it at all.
I just bought a Platinum from a power-seller in Hong Kong. I should've used the same guy that I bought MKDS, but ah well. I wasn't thinking. This ebay seller had a lot of feedback just the same and was very highly rated. Ebay does a lot with paypal to ensure you don't get scammed. If somebody has a power rating, they are doing something correct.
There's no point in going to gamestop for a used game for cheaper, because 4th gen pokemon games are 30$ used, 35$ brand new. Just pay the 5 more for the brand new game.
I went to gamestop the other day to get credit for my gba sp and some 3rd gen pokemon games, and I was looking at their used GBA games case while I was waiting... and saw a pokemon emerald version game. The only problem was that it was a green sticker with a standard gray cartridge. Suspicious much?
My point is, just be smart on ebay and you'll be fine. If you buy from a random person in HK or China, don't expect everything to run smooth. However if you buy from a power seller from HK or China, you get the same legit US version of the game for about half the price. I always e-mail them questions about shipping, etc. and I get responses back the same day or the next day (depending on when I ask because they might be sleeping).
I've always wondered why the games are so dang cheap though... but I think maybe region locking has something to do with it.