Moving mail to another folder is much slower than before (Office365)

Outlook version
Outlook 2016 32 bit
Email Account
Office 365 Exchange
We have a user that was upgraded to Office365 32-bit a few months ago (windows 7 OS). For about a week, he is experiencing slowness when moving emails to other folders, whether via shift+control+V or using the buttons in the ribbon. The delay is about 30 seconds- if he clicks anywhere else he gets a not responding message. He can then successfully move the item.
We have run updates and did an Office Offline repair. We have unchecked Add-ins and tested COM add-ins one at a time. We tried /resetnavpane and /cleanviews... When we deleted his Outlook profile, it seemed to work for a little while but the delay returned. He has no PSTs. No delay if he drags it.

(My guess is that his subfolder structure is way too big. He is moving most emails into a 4 subfolder deep tree, which then has over a hundred subfolders. When I collapsed the tree and tried again to Deleted Items, it was much faster. I suggested splitting them into A-K, L-R, S-Z and he was not going to accept that. "But it's been fine for months!")
Any other suggestions or help?