571 Delivery not authorized, message refused
That messages means a lot of things but yeah Whitelist on their Spam Filter end, Adding your IP to your SPF record, check if there is anything on the body of the message triggering the block on their end (i.e. URL or site link).
It is Office 365 with Exchange - I have created all the records that Microsoft wanted me to.
So, just to be clear, this is 100% not on my end, correct?
It shouldn't be on your end, the message is coming from the recipient's end server.