As of this morning all emails to our domain are failing, with the error "Permanent Failure: Other or undefined security status". Nothing has changed with our configurations either in NetSuite or in our email (office 365). Any advice on where to start looking for fixes?

Just starting at the top, do you have DKIM setup in NetSuite? and on the domain?