I believe fsaldain is on the right track with SPF (sender policy framework). I am an email admin tracking down a similar issue.
We use exchange and have the BB's config'd to use OWA over an SSL connection for security. I've found that when users send to certain email domains using SPF on their mail gateways, that mail bounces. however, sent via our internal network (using outlook) it flows just fine.
I did some tests and found that the BB relays the message to the destination but masquerades our domain to make it look like it came from us. (which is actually one of the mechanisms spammers use)
When the gateway receives the message, it checks OUR SPF record via DNS, finds that it wasn't sent by our actual email server and then fails.
The fix is to change the SPF record to include the list of servers that RIM uses to relay mails as servers that are authorized to send mail from the masqueraded domain. (visit spf.org to generate a new record)
However, I am looking for the list of all the servers that RIM uses so I can change our SPF record.
rmockler, you be having the same issues. ask your admin if there is an NDR generated, if so, try and see if you can get ahold of it and maybe I can help you dissect.
just saw this post while doing my research and thought it might help.