If you have installed the game on your computer and you can still get hold of your computer, I believe the key is in a file called "key" in your dominions folder.
Also you can just copy the entire dominions folder to another place. Dominions apparently does not write anything to registry (windows version).
Sombre said:
Did you have to prove you had previously bought a copy?
Fortunately, krawn had purchased the game directly from our online store. We were able to verify his purchase based on the information he provided when he created his customer support request.