Lost licences

On occasion, I have this situation where a licence has been allocated to some one who has left the company and although the user has been removed, the license seems to go into limbo and I am unable to reassign.

Any thoughts ?