Thanks for all the responses guy.
Andidarmali: Hard to do a kill/disable on a device that's not in the manager as I stated in my message the BB had already been deleted.
Ashworth: Yup saw the bug report in SP4 but we have been running the same config for over a year and I find it hard to believe that "suddenly" we expose the bug. I am considering patching but not until i talk to our provider and RIM. I have restarted BES but it made no difference which was not unexpected.
We do have A/V running on Exchange but it has been running on it since day one over 3 years ago, not likely to be the culprit now.
BBConnect: Again, not going to work too well with the user already being deleted out of AD and having no mailbox.
Obviously somewhere in the system it believes this user still exists yet they do not show up in BES or AD after having been deleted. I will see what our vendor says and try opening a call with RIM (After we renew our support

).
Something tells me I'll be patching...
I'll update when I know more, thanks again.
Mike.