I could be wrong, but I'd guess it's like this:
There's no telling how many or what CD keys will be used when the game is made, so the game is designed to accept CD keys that fit a certain mathmatical pattern. However, for online play, as each CD key is printed and put in a package, it is added to a registry of real CD keys. In this way, in theory, only people who really bought the game have a real CD key. So a key gen just makes random keys that meet the mathmatical requirements; it doesn't know which keys are registered in the online database of valid CD keys for online play.