Post Office 365 migration issue

Is it only gmail, but all other emails successful? Is it all gmail or select gmail addresses?

Only to some Gmail addresses. Microsoft has verified all the records 3 times.

Oh ok, if its only some gmail addresses but not all, that at least confirms that the gmail.com domain as a whole isn't being blocked. It may be getting caught in O365 quarantine, so if you have the email address of the account not being successfully delivered i would suggest looking in the quarantine to see if you see it there:
Login to O365 > Admin > admin centers > exchange > protection > quarantine, there you can see quarantine items and release if needed. Also do you know the content of the gmail message that was sent, it may have been spam or malware. If you have the email address you can do the following:

 O365 > Admin > admin centers > exchange > mail flow > message trace and here you can query to see if the message made it and what happen once it hit the O365 transport or not.

it has been 16 hours

What has been 16 hours ... Since DNS changes; since migration; since an email was sent?

Have you done any message tracking?

Make sure you have DNS records for SPF, DKIM and DMARC configured for sender authentication ... https://blogs.technet.microsoft.com/fasttracktips/2016/07/16/spf-dkim-dmarc-and-exchange-online/

16 hours of dns change.

check the quarantine and message trace that I suggested above and if you can see the message in quarantine, or with message trace to see if the message even made it to O365.

DNS replication is 72 hours.  There is no avoiding it.  However, it could work before then.

Take a look here to see the state of replication of your DNS records worldwide ... https://dnschecker.org/

Nothing in quarantine, no signs of the gmail email in the message tracker and the dns replication checker gave me all green check marks. gmail does not offer any support, any idea?

when you performed that trace did you perform with the gmail email address that was my delivered?

Also can you check if the sender go any type of rejections or NDRs.
If message trace doesn't show anything it's possible the email didn't make it. check with the sender to see if they receive any NDRs.

I would also have the sender send a normal test email and see what happens. the issue could also be on the sender side so if you can't find anything in o365 in quarantine nor message trace then it may have been on the sender side.

the sender is my personal gmail account, I get no ndr message, the message is sent to o365 and I get no errors.

Oh ok, are you sure you performed the message trace correctly? If it was a normal test and was successful there should be something in message trace. @Todd made a good point about DNS replication but I have never seen it take 16 hours or 72 hours for replication. I would look at message trace again and make sure you searched correctly.

ive searched using the sender email which is email@gmail.com, it did not bring anything, if there a way to trace by the domain only, like *.gmail.com?

yes it does accept wildcard also for the search.

also trace you own company email to see if it shows anything.

i was not able to to use a wildcard on the trace screen, also did not understand how to trace my own company.

In order to use the wildcard do the following, go back to message trace and select date range to search, then leave delivery status set to 'All', next click the sender button see the screen shot of dialog window when you click sender.


Type the wildcard as *@gmail.com in the 'check names' text box (second box), then click the 'check names' button and it will automatically move the wildcard address up to the 'add' text box (first box), then click ok, and and then click search. It will search for the gmail.com emails.

To search for your own personal company email address select the 'add recipient' button and the same dialog window will open. if your mailbox is in office 365 select it from the list of mailboxes by just double clicking your name or click the 'add' button, then click ok and search.
Thats it.

Ok, I have finally received a notification, by the way there is no mail.domain.com dns record anymore on godaddy, cause O365 did not ask for one during the setup. I've used all the records the O365 wizard asked, but no mail.domain.com is present anymore, that record was present in the old rackscape dns server, when emails were hosted there. I'm still not getting emails from certain gmail.com accounts, and honestly not sure if any other domain is having issues emailing me as well.

The response was:
DNS Error: 4228836 DNS type 'mx' lookup of domain.com responded with code NOERROR 4228836 DNS type 'aaaa' lookup of mail.domain.com. responded with code NXDOMAIN 4228836 DNS type 'a' lookup of mail.domain.com. responded with code NXDOMAIN

Final-Recipient: rfc822; sean@domain.com
Action: delayed
Status: 4.0.0
Diagnostic-Code: smtp; DNS Error: 4228836 DNS type 'mx' lookup of domain.com responded with code NOERROR
 4228836 DNS type 'aaaa' lookup of mail.domain.com. responded with code NXDOMAIN
 4228836 DNS type 'a' lookup of mail.domain.com. responded with code NXDOMAIN
Last-Attempt-Date: Tue, 20 Mar 2018 20:53:42 -0700 (PDT)
Will-Retry-Until: Thu, 22 Mar 2018 19:23:45 -0700 (PDT)

go to www.mxtoolbox.com and on the first page enter your email domain so that it can check your mx record. verify that your mx record is pointing to o365.

yes, it points to microsoft.
mydomain-com.mail.protection.outlook.com