I bought a license for this game when paid licensing first became available, back when it was playable without a license still but the keys were cheaper than they were intended to be when a license was required to play. How would I go about recovering this key?

It's registered with a different email account than the one used to register this account, I can ofcourse still access that email, though.

Thanks.

Anything I can do to get my key back?

You might have some luck with this old page, I'm not sure if it gives you steam keys though.
http://licensing.datarealms.com/licensing/

Not having much luck there, it's not recognising the code. Can I send my to you in an email to confirm and see how we stand from there?

I found my code on an old printout of an email about the code when I first bought it in the back of an old drawer today, so that's convenient atleast.

Send this guy an email or a PM, I'm not sure which is more effective in getting in contact with him. He's the licensing guy so he should be able to help you out.