The Microsoft Dynamics CRM team had a good article on the proper setup of Outgoing CRM email.

One additional step that needs to be performed if your Exchange Server is not on the same physical computer as CRM is to instruct the Exchange SMTP service to allow the CRM server to Relay outbound email through it.

Note: These steps mostly apply to CRM Professional installations where you are have decided to use a different server other than the CRM server to send outbound email.

A CRM SBE will have everything on one server so for normal SBE installations, this will not be an issue.

Background:

As a security measure, Exchange 2003 does not allow other servers to relay SMTP email though its SMTP server unless specifically instructed to do so. This prevents unauthorized email traffic that can turn your Exchange server into a SPAM host.

The Procedure: 

From the Exchange Sever, start the Exchange System Manager application and follow these steps:

1) Double-click on Servers
2) Double-click on the Exchange Server
3) Double-click Protocols
4) Double-click SMTP
5) Right-click on Default SMTP Virtual Server
6) Select Properties
7) Click the Access Tab
8) Click the Relay button
9) The Only the list below radio button should be checked, as shown below:

10) Add your CRM server's TCP/IP address to the list of Computers that are Granted Access.
11) Click OK.
12) Test by sending an email from the CRM web client to one of your test contacts.

If you don't follow this procedure, the Exchange Server will simply ignore any outbound SMTP email from the CRM Server and no one will be notified.

Final Note:

If email is still not flowing, make sure your Exchange Server ( the computer account, itself ) is part of the PrivUserGroup that CRM created within Active Directory.