We rebooted the BES server last night and the Activation worked after that. Not 100% what solved the problem....but to answer your questions:
-Yes, the messages were leaving the users inbox
-No the email is not being scanned in any way
- Timezone is set correctly
So, I cant positively identify the problem, but I will say that after the reboot the activation for those devices was working fine...