Dizrythmia, Waffles, you both seem to be representing opposing views on the matter. I think the actual way things work is somewhere in between, leaning on Waffles's side, though.
Waffles: I'm totally aware that the games back up their algorithms to prevent tampering, perhaps to multiple levels, and that pulling off an indetectible cheat is extremely difficult and that, perhaps, no one knows how, but I just don't believe that GF would design things so that the flagging spreads. I mean, if you trade a flagged Pokémon to an otherwise legit cart, the Pokémon should retain the flag, but it shouldn't spread; that's just wrong, and opens up the opportunity for game sabotage to go on. EVERYONE who's been in a type of community (a school, for instance) where regular trading's going on would get "flagged" and not know why, and they'd all be ineligible for tournaments and special events (not that they happen, anyway, but the point holds). Is this what Nintendo wants? I don't think so. If they did, they just wouldn't hold tourneys. Do you have any proof that, if you trade a cheat poke into an otherwise legit cart then release the cheat poke, that the non-cheated cart remains flagged? I don't think Nintendo puts viruses on their carts; I didn't think you could even trade Bad Eggs.
Dizrythmia: I'll agree that it's possible to construct a perfect cheat, but I don't believe anyone's done it yet. I don't even think any commonplace cheat devices are sophisticated enough to allow for it. (I'm not sure about this since I don't own one; they might have progressed some since the Game Boy Classic Game Genie. I haven't looked at one since.) Nintendo knows people will try to cheat on their games. They also know that the devices they use are rather primitive; limited, usually, to altering bytes of data in RAM/ROM, and that they are blind to what data's already there. (extremely pathetic from a developer's sense) Therefore, Nintendo can easily put in checks to prevent many types of cheats from happening. In fact, I believe Nintendo is letting us cheat. Instead of locking things down, altogether (which would likely just hasten the development of more sophisticated cheats (beyond the level of Gameshark/Action replay)), they let us cheat, quietly slipping in flags (invisible ingame) that would slip under the radar of the people developing the cheats. Since it seemingly does nothing, why try to defeat it? (not to mention that defeating it would also be beyond the level of commonplace cheat devices) Unless you've actually taken a look at the assembly and understand it, or at least properly inspected the save file plus Link data sent in trading, don't assume your cheats are flawless.