hello Chertio,
may i make a wild guess that you used steam, gamersgate or anything like this?
And now you might be confusing the internal "key" for the online distribution with the one for Paradox registration.
i think i remember from posts that for gamersgate for instance they used even one part of the serial number with SIX fields...
for this issue there are some threads explaining how to deal with and in the worst case, you have evidence that you bought it (whats obvious, as you have a key, as you mentioned), the lads from Ageod would help you out either...
see for instance:
http://www.ageod-forum.com/showthread.php?t=21671
since you wrote that you are running 1.01e, you can find a couple of newer patches still in the forum here, but not the latest "state-of-the-art patches".