If it’s a domain user, re creating the account, won’t resolve the problem.

STSADM -o deleteuser, STSADM -o migrateuser and any removal of user from the UI will fail to clean out the userinfo table.

Check if my site for the user exists, if so, please remove it and restart IIS to clean the cache and test the issue again.