Is your exchange server the outbound smtp server for your network? or do they have pop3 accounts on the outside for internet mail? You might want to configure a forwarding smtp server onto your exchange server pointing to your upstream providers mail server.
I am still not quite awake... sorry... OK... it sounds as though you need to make a new connection document on your domino server to forward smtp mail to the Sun server. What is most likely happening is that when the handheld sends out an smtp message, you domino server doesn't know where to route the message to. You have to explicitly tell the domino server where your outgoing mail server is... which is kinda strange if the people inside the network, ie using desktops, can send outside mail.
Can your inside desktop users send outgoing mail through notes? If they can, there should be no reason why the BES server isn't sending the mail out. If the inside users can't send mail through the domino server, you are going to have to configure that. As soon as the Domino server can forward internet mail out onto the internet and have it delivered, the blackberry's will follow suit.
We had the same issue and it involved adding a connection document for the smtp to the internet as well as editing the configuration document mime settings. The best thing to do is if you still have lotus support, call them up. They are very helpful. They provided me with the solution for our environment