Are you sure you are entering it in the right game's field in My Games? Between all expansions and editions, it can be quite confusing - for example an EU3:Complete code will only work in the exact EU3:Complete game's entry field, not in the one for EU3 or EU3 Chronicles. Similarly with almost all base games, expansions, and collections - generally each one has its own separate field for key entry.
EU4 has three separate fields in MyGames:
- EUIV: Call to Arms event
- Europa Universalis IV
- Europa Universalis IV: Pre-order
The first of these has a separate key you should have received by email with any other CtA bonuses you earned for the pre-release promotional activities. If you did not earn that bonus at the time there is no way to get it now.
The other two were intended to give a special forum icon to those who pre-ordered. However there turns out to be no way to differentiate the keys given out to those who pre-ordered and those who didn't. So only those who registered before game release get the Pre-order icon, everyone else gets the standard one.
If you still can't get it to work, please submit a ticket at http://paradox.zendesk.com and include your key as well as what EXACT game(s) you have (a surprisingly large number of people forget this rather vital piece of information) and where you bought/downloaded it from.
You should also check and re-check that you are typing the key in 100% correctly, and are not confusing 0/O or I/l/1 for instance. Pasting the key in from your clipboard is best of course.
2016 UPDATE:
we are moving away from the key system for games on Steam. The CD Key link may well be empty now. Instead link your Paradox account to your Steam account here
https://accounts.paradoxplaza.com/profile/email
then go here
https://forum.paradoxplaza.com/forum/index.php?account/owneditems
and hit the Sync Owned Items button. All Paradox games you have on Steam will be registered automatically. Non-Steam games will still use the Registration Key system.