My best guess here is that the directory facing account in your new installation does not have rights to update (delete) properties on that user - specifically the Unity properties. It'll be deleted for a few minutes and then the directory monitor will pick it up again during the next synch - that's just a guess though.
What version of Unity is this? You can try using the Remove Subscriber Properties tool to clean that guy's account in AD of Unity properties and it'll be removed - you can log in with a domain admin account or whatever to make sure it has rights to do that - you can get this tool off www.CiscoUnityTools.com - it's also included in the Global Subscriber Manager if you're running 4.0(1) or later - go to the import subscriber page and you can clean properties off users in the directory from there (it uses the same method as the remove subscriber properties tool).