CD keys aren't embedded into the software. You manually enter the CD key, which is then verified online. Simple as that. In terms of whether it'd be 'expensive' to do, I don't know, I'm guessing that you're right in that it shouldn't be very expensive to do, but the fact that it has never been done makes it incredibly unlikely that it is being used in this case.I don't understand how some are saying programming unique IDs for each cartridge would be too expensive. They could easily have hardcoded a unique ID into the eeprom/save system or stored in the read-only boot code chip that handles the cartridge communication protocol. They can simply program their factory machines to code a different ID for each chip produced and they are then passed along in the production process to be soldered to the game board at a later stage in production.
It would serve that purpose so as to identify that game's serial to the online system. It's no more difficult then programming CD-Keys for Windows OS and using activation checks to prevent two from being activated at the same time on different machines (Lets pretend the activation cracks and piracy stuff is not a factor for this comparison).
Nintendo can then detect if two games are online that share the same ID. Then it's simple. both get banned and any future instance of a game/rom using that ID.
It's also possible game roms lack this ID completely since it could be stored in a different chip. Lack of ID equals auto rejection from any connection to Nintendo's online system.
That's not to say it's fool proof. Gateway could spoof that ID like one would spoof the region/firmware version. But it would be difficult to pull off since the online servers store all the valid game IDs and thus it would reject an ID that doesn't exist. Duplicates also get rejected and results in bans.
Remember how Microsoft can ban hacked Xbox hardware? I'm pretty sure Nintendo can do the same if they wanted to.
Banning the Xbox hardware is a totally different issue to having IDs in the game itself.