UPDATE:
Right, so i contacted Steam and i was initially stonewalled, again, but after replying to them again i have actually got somewhere. Heres a copy of all the messages they've sent me.
Me:
Hi,
I should have a CD key for Lead and Gold: Gnags of the Wild West and i cannot access it on my steam account. I need it to register it with Paradox (the publisher) and would very much like to do so. If you could please sort this out or supply me with a CD key then it would be very much appreciated.
Thank you
Them: Thank you for contacting Steam Support.
There is no CD Key required for Lead and Gold.
You have it registered on your account 2dme and you should be able to download the game directly from your Library > Games list.
If you have any further questions please let me know.
Me:
Yes i know, the point is the game is supposed to come with a CD key so that i can register the game with Paradox, not just Steam. I know i can still play it and its registered to my Steam account but i also wish to register it with paradox in order to get the benefits. I understand that you previously supplied people with CD keys for Lead and Gold but stopped doing so after the free to play weekend for it. I also understand that Paradox have contacted you about this problem and also want it resolved.
Them:
Hello Paul, Unfortunately Steam Support does not handle these type of issues. I will send an email to the Steam team for further investigation.
Then a minute or so later they completely changed there minds with this message...
Hello, We are investigating this issue further. As soon as we have more information, we will update your ticket
SO it looks like theres hope for those of us who still don't have a CD key. Thought i'd let you all know.