You need to do two things to free up the licence.
1) Get the user to deactivate his licence in Tableau Desktop see here Move or Deactivate Tableau Desktop. This will send the information to Tableau to adjust the licvence availability. For completeness I would then get the user to uninstall Tableau Desktop too.
2) Delete the info you have against that licence key in the Customer Portal.
From experience, 1) is key in ensuring Tableau's data stays in sync with yours. I've had numerous occasions with users who no longer need the licence and I've then redistributed into the business. Sometimes by the time I find out they no longer need it, they've no longer got the machine they had it installed on, or the machine has been restreamsed so they're unable to perform the deactivation step. On rare occasions when the key has then been reallocated to someone else, that new user has had issues registering the key as Tableau believe its already in use. Tableau Support have to get involved to fix their data, and I've always been told to ensure the deactivation step takes place.
Jonathan - I can't comment on how Tableau Online works. I would imagine this is something your Tableau account manager can advise on, and suspect it's something Tableau themselves will need to resolve for you. I am going to attempt to branch your question to a new thread, as this is techinically a slightly different question from Sid's and it will have a different answer (a thread can only have 1 correct answer).
Yes, Please be sure that the Tableau Desktop software has been deactivated by the user as mentioned above.
One additional thing to note is that the Registration information in the Tableau Customer Portal cannot be removed. It is a piece of data captured that is just a record of history of the life of the key. It is possible to remove the user that is assigned to that key by editing the key:
Let me know if there are any additional questons!
Thanks Kelly - what you describe about editing the key in the portal is what I meant by deleting... you edit the key and remove all the info shown :-)