How do I refresh the Office365 Exchange domain settings on Godaddy?

Question

User1 can't seem to send emails to another user (User2) in the same Office 365 account. I can send email to and receive email from User2 from an outside account. I'm also having no issues getting email from the User1 account. But User1 keeps getting messages bounced back from User2 with the following error:

Your message couldn't be delivered. The Domain Name System (DNS) reported that the recipient's domain does not exist.
Contact the recipient by some other means (by phone, for example) and ask them to tell their email admin that it appears that their domain isn't properly registered at their domain registrar. Give them the error details shown below. It's likely that the recipient's email admin is the only one who can fix this problem.
For more information and tips to fix this issue see this article: https://go.microsoft.com/fwlink/?LinkId=389361

When I do a message trace for all failed messages, and I click on one of those messages, I get the following error:

Status: Office 365 received the message that you specified, but couldn't deliver it to the recipient (‎someone@Company portal .com‎) due to the following error:<br /><br /><b>Error:</b> ‎550 5.4.310 DNS domain contoso.com does not exist [Message=InfoDomainNonexistent] [LastAttemptedServerName=contoso.com] [MW2NAM10FT006.eop-nam10.prod.protection.outlook.com], InfoDomainNonexistent‎<br /><br />A non-delivery report (NDR) message was sent to ‎thesender@Company portal .com‎. The NDR might provide more details about why the email message wasn't delivered and how to fix the issue.

More information: <div>Ask the sender (thesender@Company portal .com‎) to follow the instructions in the NDR to fix this issue. The NDR might also include specific information for email admins. If the sender is unable to fix the issue, ask them to forward you the NDR and then follow the guidance for email admins.</div>

I've been looking over the DNS settings at Godaddy and they seem okay. They of course think it's something wrong at Microsoft.

I'm not exactly sure how I'd refresh all the MX and related information on Godaddy. I think some MS process did that for me originally.

Any ideas about what's going on?

Answer 1

Yes, they are both in the same tenant. I not only rechecked the spelling, but I also used the online interface for User1 to send a message to User2 and it bounced back. And again, I sent emails to User2 from my own tenant (I'm with a tech support service) and the message was received. One thing, I had User2 send an email to User1 - no problem, and then I replied and it went through with no problem!

So:

1. It's not User1's Outlook (since this happens both from Outlook and the online interface)
2. There are no mail flow rules for either user.
3. I have no problem sending and receiving from either account from an outside email address

I'm guessing that I either have to delete User1 and then reinstall her (that would be very bad for several reasons) or at least redo all the DNS info at GoDaddy (much less harmful but I've never re-installed a tenants' DNS info on GoDaddy or any other ISP for that matter + I don't understand how DNS settings could cause problems for only one account!)