We have installed a new 2008 Server and installed Exchange 2010 to replace Exchange 2003. The AD is 2003. Once the install was complete and we redirected the incoming port 25 on the firewall to the new server, we moved a couple of mailboxes for testing. In that transition state, all incoming email was rejected (550 5.7.1 Unable to relay).
If we changed the incoming firewall rule back to the 2003 server, mailboxes still on 03 could receive incoming, but not the mailboxes on 2010. The 2010 could send email, but not 2003. When a 2003 user tried to send outbound email, we noted on the 03 event logs that the new server was rejecting the email, again unable to relay.