Symptom:

When configuring incoming e-mail, the e-mails come through just fine if the server name is in the e-mail address:

[email protected] but when you change it to a vanity name [email protected], the message is bounced back and you get this error:

Delivery has failed to these recipients or distribution lists:

[email protected]
Your message wasn't delivered because of security policies. Microsoft Exchange will not try to redeliver this  message for you.    Please provide the following diagnostic text to your system administrator.

The following organization rejected your message: servername01.fqdn.com.
 
Problem:
The SharePoint server relay rejects the message because it doesn't recognize the name.  You have set it up in Exchange, but you need to set up an alias in the SMTP service on the SharePoint server;
 
Solution:
Configure an Alias Domain

An alias domain is an alias of the default domain. You can set up alias domains that use the same settings as the default domain. Messages that are received by the SMTP Service for an alias domain are placed in the Drop folder that is designated for the default domain.

To configure an alias domain, follow these steps:

1. Start IIS Manager or open the IIS snap-in.
2. Expand Server_name, where Server_name is the name of the server, and then expand the SMTP virtual server that you want (for example, Default SMTP Virtual Server).
3. Right-click Domains, point to New, and then click Domain.
4. The New SMTP Domain Wizard starts.
5. Click Alias, and then click Next.
6. Type a name for the alias domain in the Name box, and then click Finish.
7. Quit IIS Manager or close the IIS snap-in.