That is a weird spot to be in, I have had to deal with similar issues before, and these support issues that are widespread, but somewhat random can be the worst.
I would be interested to know when you say profile (windows) based, if that is the entire machine, just their outlook profile, etc.
1. Does their OWA load and function fine and at a speed you would expect?
2. Does https://testconnectivity.microsoft.com/ from their machine work as expected (run the outlook connectivity, and outlook autodiscover tests). Are you seeing quick response times there or slow?
3. If you setup a new email profile (not windows profile) does that fix the issue?
The above 3 things will help to narrow down the problem.
- If all 3 are slow, its probably something related to their network/firewall (even at a machine/windows level), and tinkering with the applications etc probably wont help.
- if the testconnectivity works, but owa is acting funking, it could be mailbox specific on the exchange system
- If the testconnectivity and OWA are quick, but outlook profile helps, then im guessing old cached information is stored in their outlook, and a fresh start would be good
Outlook is a fickle thing. Most of the times I have dealt with issues like this, the specific outlook profile they have is just running sluggish and slow, and a new one almost always helped. Its not ideal, but sometimes outlook profiles just stop working great, especially after migrations.
I would try those things for a few users, see if you can find any consistency, and try to narrow down the problem to a specific area. Unfortunately I think you are likely to find outlook as the culprit, and a new profile to be the easiest path forward.