Exchange Server Address Resolving to Random String

You really don't want a mail server on dynamic IPs, you can't set a PTR(look like spam), its listed as a dynamic IP(big spam flag) and you'll lose emails while DNS is updating. I highly advise you get a static IP or get email service Google apps(which you can get free) is quite nice.

To answer your question just set up 2 A records and point each to something like mail.domain.com & .biz.

Exchange 2013 CAS can proxy/redirect access to your 2007 mailboxes. You don't want the ExternalURL to be the same on CAS servers for both versions though. Your Exchange 2007 servers ExternalURL should be legacy.mycompany.com, and the 2013 CAS servers can continue to use webmail.mycompany.com.

You want to migrate CAS/transport to your new servers first, which will proxy/redirect access to your old mailbox servers. Once you verify that you can access mailboxes residing on the new and old environment and the new environment is handling bidirectional mail flow, you can cut over DNS. Then you can move mailboxes until you've cleared out the 2007 environment, at your leisure.

While I haven't yet done a complex 2007 to 2013 migration, I have done 2007 to 2010 and 2010/2010 site migrations. The following document should give you some helpful guidance around coexistence and how to properly configure it: http://technet.microsoft.com/en-us/library/bb310763%28v=exchg.141%29.aspx

Please let me know if any specific configuration questions come up.