Are you trying to activate using the same Windows Live account you originally used?
Double check, because if you have 2 Live IDs, it may default back to one used for say, Messenger for example if its different from your GFWL account.
When you activate your game with GFWL, it should be tied to that GFWL account (or Windows Live account)
From my understanding you get 15 total activations.
Sadly, Im uncertain if that means a re-install means a activation.
I have noticed, that when you first install a game you automatically get logged out of Live on first start with a "CD-Key Invalid" message or something along that line the 1st time you boot the game (In the case of a clean install)
1) Make Sure you are logged into the correct Windows Live Account in the Game.
2) When it shows that message, Press 'Try Again"
3) Put in the CD-Key STEAM gives you for GFWL
At this point it "should" check that with your account and update everything wth the appropriate unlock certificates needed.
If that doesn't work, try calling them to resolve the issue: http://www.microsoft.com/games/en-US...ctsupport.aspx