Gameboy
Many people can catch there Pokemon using Gameshark. One way to check if they have been caught illegally is to check where the Pokemon was caught by checking it's info, like that Feebas can only be caught on Route 119. (I searched and searched and finally found it after 2 whole hours) Another way is to check what kind of PokeBall the Pokémon was caught with by looking at it's info and seeing what color the PokeBall is, masterball being a purple one. In the game, I think that you can only get two masterballs at the most. I have gotten both of them by winning that one Trainer ID contest and getting one at Team Aqua's hideout. So, if all of there Pokémon have been caught with a master ball, you know that they did something to cheat.
TCG
For the TCG, each card has an ID number on the bottom of them that should be similar or exactly the same as the other cards in the booster pack they came in. For example, if you get a Mudkip and Skitty in the same pack, they should both have the same or similar ID numbers.
Personal Experience
During the R/S Challenge at San Diego, I battled one kid who was undefeated and remained undefeated. When he got out his deck, he asked me if he could switch some cards with some others, which you can do. Now that I have thought back to this, and I remembered that I looked away or something and was watching something, and he put his deck on his lap and went through his backpack. Unfortunately, I had not checked to see what he did and now I remember that he kept getting Manectric and Electrike during the game, so he could have added one too many cards in his deck or cards that he had got at another time, and not during the beggining of the tourny when we got our 6 packs. I am not accusing this person of anything, not that it would matter now, but I now find it kind of suspicious how he kept getting the same Pokemon, with an occasional different one. Anyways, its way too late now to accuse anyone of cheating and hey, I'm happy because I came in first for my division and just got the code to buy stuff at PokemonCenter.com, so I ain't complainin.