We recently migrated over to Office 365 and everything is working fine apart from one user.
The user is able to e-mail internally and externally fine but sometimes when another user outside replies back to an e-mail that he has sent, the end user gets the following bounce back:
The e-mail address you entered couldn't be found. Please check the recipient's e-mail address and try to resend the message. If the problem continues, please contact your helpdesk.
The following organization rejected your message: company.com
company.com #<company.com #5.1.1 SMTP; 550 No Such User Here"> #SMTP#
The strange thing is, sometimes it will work fine but sometimes it bounces back. The user exists.