Great! The large organization I support does have a way to delete mobile devices, but
my client uses Office 365 and his account doesn't have a way to delete his own devices.
Even the company that supports him was not able to do it, and had to open a ticket with Microsoft.
The insight is that there's a threshold on the number of mobile devices that can synchronize with the mailbox. Once you exceed it, weird things could happen.
And thinking about, most people just add their new phone or tablet and don't know they should remove their old devices from the list.
In my client's case, I still suspect some sort of corruption with the device list; hopefully Microsoft will be able to fix it.
If this was a real issue with iOS 13, the news about it would have gone viral already.