Lance-
This is not really backup exec troubleshooting any more, but I've run into this a number fo times so let me try to help you out.
A mail server is relaying when it accepts mail for a domain for which it is not an authoritative mail server. For instance if your domain is foo.com, any mail bound for bar.com sent through the foo.com server is relayed.
You get the "relaying not permitted" error for good reason; mail servers should be very picky about what they will relay in order keep spam down. However, if you REALLY mean it, you can set your exchange server to allow relaying. Note that you should NEVER OPEN RELAYING FOR ALL DOMAINS. EVER. You will end up on several spam blacklists so fast it'll make your head spin, and you will justifiably have trouble getting back off of them. You have been warned.
Anyway.
The right way to do it is to tell the foo.com exchange server that bar.com is an "accepted domain". A good discussion of this can be found here: http://msexchangeteam.com/archive/2004/10/14/242310.aspx (The same concept applies for other mail servers than exchange, by the way.)
(As an aside, it is generally a good idea to have your mail server insist on authentication before accepting smtp traffic, but your environment may make unauthenticated smtp for a limited number of accepted domains a reasonable risk.)
There may be another layer of antispam to overcome once you have the relaying sorted out, so if the BE test message doesn't flow, then test again with telnet.
Emjoy.
