@Lachlan Bunter -
This one was frustrating. I never received any explanation from MS as to the issue and the case was closed without my knowledge or approval at the end of September. We are no longer having the problem - so i assume whatever fix they said they initiated in August, that took until September deployment window, was the solution for my tenant.
If you haven't, i would open a case with MS directly.
Sorry i couldn't offer any other information/help.
Dianna