Check in the bulk subscriber delete tool. If the users is still showing up in there, then this is why it's still using a license. It also takes a little bit for SQL and AD to replicate and update each side.
If you are still having issues, I would restart the Unity services on the box. Then check licensing and see what you have.