Exchange 2003 & Godaddy Migration to Office 365

Question

Here's a decent project I'm about to tackle, thought I'd double check with you folks.

Here's the scenario... Existing AD DS with Exchange 2003. They decided to upgrade to Office 365 Exchange. Microsoft has well documented instructions on how to migrate this, little concern there. The domain is registered with GoDaddy and all email accounts are hosted there too... reason being is sometimes the office of the server loses internet connection (ISPs fault), so the 2003 Exchange is configured to pull emails from GoDaddy every 15 minutes.

Microsoft has also documented the migration of email accounts from GoDaddy to be as simple as using their 2 minute DNS migration tool - very cool.

Would it be logical to assume if the Server 2003 Exchange data hasn't been imported to Office 365 and the DNS records are updated, the emails won't have anywhere to go and breakage occurs?

What would be the correct procedure here? Migrate the Server 2003 Exchange using Microsoft's tutorial, kill the old server, then run the DNS update tool on GoDaddy?

Thanks for your time!