We seem to be having the same exact issue as above, in that, the user exists but "doesn't".
We have tried the below fix, but unfortunately to no avail.
The Exchange account is fine, can log in through Outlook, OWA etc, but BES just can't add the user in again. We are using BES 5.0.1 running on Server 2008, Exchange 2007 on Server 2008 and the AD environment is on 2008 servers with 2003 compatibility. SQL database is on a seperate server running SQL 2005 on server 2003 SP2.
We also realise BES have removed the SQL job RIMpurgedeletedUsers as of BES 4.6 SP5 - is there anyway of adding this job on manually maybe?
Any guidence to resolving this would be much appriciated,