It is as the BES doesn't know the user exists because the BES is supposed to see that email when it comes in and based on that send service books and generate keys for the deive and activate it, but the BES is not getting that email. That is why I mentioned permissions. I don't know how it is in Groupwise but in Exchangge if I remove someone, I get asked if I want to remove all BB information from the mailbox. I would say yes in this case so I would then be creating a completely new account when I recreated. You may even want to bounce the BES after removing the users as well.
I don't think it has anything to do wiht the device because the activation email isn't even making it to the BES. You need to focus on his mailbox connection to the BES.