Dont know, why the Messaging agent terminates, but, have a closer look in the Logs folder which is in the Applications folder of the BES server, maybe you find more then just the "failed to retrieve the Server DN" - which means then BES is unable to locate the Exchange server.
Is the Windows Firewall on - turn it of to check if this makes a difference.
Is your DNS and WINS server working properly ?
Recreate the MAPI profile for the BES user:
KB10285 - View Document
regarding the Active directory permissions, try to use a program from rim:
http://www.blackberry.com/DST2007/pa...Permission.exe
Also, add the besadmin user manually in the exchange console the send as permissions to the user(s)