Is the user a member of any groups with evelvated permissions, such as an administrator group?
I don't know that I'd go so far as to remove the user from AD and then add them back. That could have very serious consequences.
Have you tried removing the user from BES and re-adding them?
Have you examined the BES logs to see if there's anything indicative of why the user is having activation problems?
Has the user ever tried to install Desktop Manager and mistakenly set it up for Desktop Redirector?
Honestly, it still looks like the user has some type of AV filter on their email which may be causing the activation to become malformed when it hits their inbox. That could still be the root of your issues.
What exactly happens on the device when you try to EA it?
Have you gone through the RIM troubleshooting steps for Enterprise activation? BlackBerry Search Results