Item #0. Is the Exchange server a member of your domain? If not, how much functionality are you able to utilize?
Item #1. If your Exchange server is being hosted by a third party, they obviously have admin rights to Exchange. Therefore, they have access to all your mailboxes. If the firm is the least bit reputable (and wants to stay in business) they won't go prying without direction from your corporate legal department. None of the emails will be encrypted unless you have provided your users with certificates and they've used them to encrypt their messages. Since you have an internet connection that is fast enough to handle the traffic to the external server, I would strongly recommend bringing the server in-house - and install Symantec Mail Security if it doesn't have it already. If you don't know how to manage Exchange 2003, get your employer to send you to a class. Of course you'll have to add the server to your backup scheme.
Item#2. Blackberries don't have the native ability to open signed or encrypted messages, but you can get a module that will give them the ability to do so. If you were to switch to something along the lines of a Sony Trio, you wouldn't need a BES server at all, as Exchange 2003 can communicate with them directly.