Hey everyone.
So, after doing every step that everyone gave, and after six and a half hours on the phone with a million people the problem is now resolved.
DBUtility is available from Blackberry's support team and is installed on the user's computer. It should almost never be used, so that's why they only send it after a support call deems it necessary.
So that's the answer, use DBUtility to clear out the links between user, BES and exchange. That is of course after you run everything that you all suggested first.
What a long day... Too bad I have another four hours to go on my shift.
Thank you all very much for your help. I will be frequenting these forums on my daily romp through tech links...