I have tried using all caps with and then without dashes.
I have tried using all lowercase with and then without dashes.
I have tried running crysis2.exe as admin.
I still have to put the serial in every time I start the game and want to play MP, and even then I am lucky to get into a game without seeing "serial key in use".
I need an answer from EA or Crytek please, because you cant get money back for games on steam.

Try clearing your browser cookies and then log back in. Enter the serial number at the login screen instead of entering it when you load multi-player. See if that works.

I had the same problem.
To fix it all i did was..
(enabled third party cookies, don't think this has anything to do with it but yeah)
-Ran as admin
-entered the code in before logging in.. all lowercase no dashes (even though it says to)
-logged in and it saved my code permanently with dashes

i also can join servers now.. couldn't before.