I have installed a new Exchange 2010 server that cannot receive emails from mailboxes hosted on an Exchange 2003 server.
I have verified that the permissions are setup to be anonymous, exchange users, exchange servers, and legacy exchange servers for both the default properties and the client properties in the console.
I do have an environment with a Barracuda Spam Firewall. This is setup as a smart host on my exchange 2003 box.
The Exchange 2010 box I have gotten to successfully be able to send emails to the internet and to the Exchange 2003 box.