One thing that's giving me some problems is my anti-spam service, which greylists unknown emails the first time they go through... Sometimes the message sent by the device to the BES is delayed 10 minutes, allowing the enterprise activation procedure to time-out.
I just go into my anti-spam console and white list everything from *@*.blackberry.net and that does the trick.
Once the handheld is registered, everything's cool...
Hope this helps