In you DNS Server, create a Zone and an MX record that resolves mail.yourcompany.com to the IP Address of your SMTP server. Then create a recipent policy in Exchange that points the SMTP policy to @yourcompany.com. In ADUC, for any user, go to the E-mail Addresses tab and check the "Automatically update e-mail addresses based on recipient policy." What this will do is take the users logon name and prepend it to the address (jdoe@yourcompany.com) Does not matter what your AD name is. Two things must be in place for this to happen. The user must have a mailbox and you are using the ADUC that is supplied on the exchange CD.
This is not the only way to do this as there are many ways to skin a cat, but I think you will find this helpful.