If you're trying to relay via the Exchange Server (in other words, have it deliver mail to a domain it does not control), it's possible someone has reset the relay configuration and switched this behaviour off. An Exchange Server will accept mail in its default configuration for any email domains it is authoritative for, but for security reasons, it won't relay mail for other domains (this would turn it into a server abused by spammers).
What version of Exchange is the Exchange Server running, and how do you want to allow relay?
Probably the easiest method is to allow your web server's IP address to relay via the server. If Exchange 2003, do that by editing the SMTP Virtual Server and changing the Relay settings. More information at
http://www.quantumsoftware.com.au/support/kb/Article.aspx?ID=50.
In Exchange 2007, this is a little more difficult. You'll need another Receive Connector, configured to accept mail from the web server's IP address, and with permissions granted to allow relay. See
http://exchangepedia.com/blog/2007/01/exchange-server-2007-how-to-allow.html. Be sure to read all the security notes and ensure you understand what you are opening up before proceeding. Those notes should also apply to Exchange 2010.
-Matt