Okay, here's my issue. First of all, I'm not using exchange, I'm just using regular W2K3 Enterprise. I posted it here to make sure that it would be treated as a mail issue.
I have relaying setup to allow anyone within the network to relay. I have authentication through Active Directory. the e-mail name is phoenix@(domain)
I can send and recieve internally, and recieve externally, but cannot send externally. No matter who I send the message to externally I always get the "Delivery Status Notification (Failure)" when I send.
I would appreciate the help, thank you