Outlook resolving to old exchange server

We migrated to Office 365 from our Exchange on-premise server yesterday. We are experiencing a problem with many PCs where, on the PC of a user for whom we are setting up an Outlook profile to connect to their Office 365 account, we have to change that PC's primary DNS server to point to a DNS server outside our facility or else the it will try and set their mail server to the old mailserver even though we've added all the DNS records that we added on the public DNS servers to our internal DNS server.

We are setting the PC's primary DNS server to 8.8.8.8, configuring their outlook profile, then setting their DNS back to DHCP. That seems to work for setting up the profile.

But, after a while, the server name on their email profile will change from something like this
8b97ea0e-56db-419a-923a-a54ce7d8a86d@whitewater.com, which is the correct thing, back to the old on-premise server SERVERMX2.relyonus.local

What am I missing? Why, despite our internal DNS records pointing to Office 365, is Outlook wanting to badly to resolve to the old mailserver instead of Office 365? Is this something in Active Directory?