Two+ weeks later, mail is still streaming through the old gateway. Actually, at this point, I'd estimate that the load is about 50/50.
TTL (time-to-live) on the DNS records is 1 hour, and has been as long as I can recall. When I do a dig from outside the office, everything looks fine, so I know my DNS is responding correctly.
Removing the old gateway from DNS didn't help at all. People started moaning about not getting mail
I thought that once the external MTA saw that the MX was offline, it would at least try to send through the failover
What's really weird is places such as Hotmail
I did a TCP dump on the DNS box today, and it sure looks correct to me.