Before we get into the question, here's some context that I believe would help y'all to understand my situation better:
My domain (foo.com), is owned by Network Solutions (NS), same for the DNS record.
I have a mail server (Server A), running Exchange 2010 that handles all my mail flow for foo.com and other domains.
Recently, the MX record for foo.com has changed to point to Office365 (O365) w/ the necessary settings (v=spf, etc). That is, I'm attempting to migrate my mail services to O365.
Migration to O365 has been fairly straightforward and it seems to work for the most part using the internet w/ my Outlook client (Laptop X). But...
Issue: As soon as Laptop X is on-premise, connected to the same network with Server A, any attempt to send a mail to a mailbox for foo.com would result in the unrouteable address error.
Example
Suppose Laptop X is not on-premise, say at some coffee shop, it uses the address john@farm.com (mail services for farm.com is handled by Server A) to send a mail to may@foo.com (mail services for foo.com is now handled by O365). May, who is working at foo.com (suppose its at San Francisco) would receive the mail.
But,
If Laptop X is on-premise, sharing the same network w/ Server A, the same attempt above would result in a unrouteable address error.
My attempt to fix this error
I tried clearing the cache for Server A, in hopes that it will update the delivery route to foo.com, but it failed. I have also included the error message for your reference. Any suggestions or guidance would be appreciated. Thank you, guys!
I don't know why Stack Exchange labeled the error message as spam,
but I've included the error message in a picture (link below).
https://i.stack.imgur.com/JvODX.jpg