Yes, those articles you mentioned pretty much take care of what you would need to do. How are you sending/receiving e-mail externally? Are you using an Exchange Edge server, or something else? I recently had to do something similar to this because I'm moving my company over to Exchange 2010 from a third-party e-mail system, and both have to exist at the same time for a while. I have a Barracuda spam filter for external mail, but you should be able to do the same with whatever you use. This will also be dependent on the Exchange 2010 server being able to handle the mail for both sides because I know Exchange 2010 has the features I needed to use.
Set the external SMTP server to relay all mail (both old domains and the new one) to the Exchange 2010 server. You can then use those articles to set up Exchange 2010 to have the 2003 old domain and the new domain as internal relay domains, and you can relay all mail using the Exchange 2003 old and new domains over to the 2003 server using a send connector. Using this article, you can set Exchange 2010 to allow your users to receive e-mail on their old domain, and set the default reply-to address to be the new address. This will allow for sent e-mails to show the new domain.
The last piece would be Exchange 2003, which I unfortunately don't have any experience with. Hopefully you can apply similar settings to have the 2003 server relay mail for the 2010 old domain over to the 2010 server, and use the correct e-mail addresses. You would also need to relay the new domain over to 2010 for accounts that don't exist on the 2003 server.
If your bonus question is because there is a possibility of upgrading 2003 to 2010 first, this might be the better way to go. However, I only say that because I am unfamiliar with 2003, so I'm not sure how possible my solution is in your situation.