550 not permitted to relay error sending to new Office 365 email accounts

An IT technician migrated a customer over to Office 365, including using the hosted Microsoft Exchange service for email. He followed the right steps, verified their own domain name, adjusted the MX record and added the right SPF entry. However, some people sending to this email domain were receiving a delivery failure report error (though…