The following error was experienced:
There is currently no route to the mailbox database
This can be seen in the message log with "Get-Message | fl"
The messages simply sat in the Unreachable queue on the Exchange 2010 server.
This error generally means no routing group connector was made between the two servers. However I confirmed the routing group connector was created by Exchange Setup automatically.
Next I removed these routing groups and recreated them with new ones through PowerShell:
After recreating the routing group connectors you must restart the "Simple Mail Transfer Protocol" service on Exchange 2003 and the "Microsoft Exchange Transport" service on Exchange 2010.
This still did not resolve the problem.
Next I started checking permissions of Exchange container objects in the configuration partition within Active Directory against a default install of Exchange 2003 in a test lab. I noticed that permissions on the Exchange 2003 object in Active Directory was no longer inheriting from the Administrative Group/Servers Container.
After re-enabling inheritance using ADSI Edit over the Exchange 2003 server object, this resolved the issue.