People decompile the game or program, and sees how the product key algorithm works. From there they make a generator app, and distribute either the tool, or the generated keys. And that is why you get on rare occasions, a person that buy a game or program, and the key is already in used, and requires to go through some trouble (contact the company, show proof of purchase), to get a new key or new product.
This happened to me when I bought the half life blue box! The key was already in use, even though I had just bought the game!
Now that the question you really want to ask i.e. Where do companies that sell game keys obtain their keys from. People might be able to give you an answer. They buy them from distributors, pretty much the same way people by the hard copies of software.
Yea im confused by this question? Illegal key gens? or legit keys? I looked into possibly running a website to sell game times for things like WOW and EVE etc, i barely got any useful info back from the corporate offices, EVE i did manage to get an actual email to speak to someone direct, but they assumed i already had some sort of online shop, when i said i was looking at starting one they wouldnt help. I even went to an exisiting shop asking how the procure the keys, they just said "why not join our affiliate program instead..."
This also happened to me when i bought Left 4 Dead 1, had to send steam a scan of the serial no on the manual and the receipt with my steam username on, annoying to say the least. Took 3 days to come through, a bit annoying when you buy on day of release to play then cant -_-
slightly off topic but ive always wondered how people sell used steam games on things like amozon etc.. when the keys have probably been used?
