I would email G2Play again and tell them you have tried installing the game but were unable to use the CD key to activate it, request clarification on what the exact distribution this CD key is for, and try to invoke the money back guarantee again.
You really shouldn't need to download every version of the game to try. Besides, if the page they are selling the key on is in English, and they don't mention anywhere that it is only valid for the Klingon localization released in Monaco, or something, then that would help your case for a refund.
IIRC Paypal's time limit is 45 days to file a dispute, and credit card companies should be a good 30 days after the statement, or so. Since there are no shipping times involved to send anything back for a replacement, there shouldn't be any delays long enough to get past the deadline.
Personally, I'd try to resolve the problem directly before contacting Larian. G2Play may be more reasonable before third parties get involved... or not, but you don't want to escalate the situation before seeing if the (implied) threat of escalation will work.
