EAS can be heavily dependent on proper DNS - as outlook likes to refresh it's connection information from time to time. We have found Outlook not stripping the trailing period off of server names when autodiscover is used - causing clients to fail to connect and sync properly.
There will most likely be issues with cached profiles. Then consider whether NEW outlook is in use, or old -- as there are various problems between the two.
There are a whole myriad of issues that can be encountered. Making sure your logfies are set to "Detailed" for the protocols in question may help at least diagnosing what's causing the issues.
There could be import problems bringing the data in that did not import properly - but that may not show it's face until the client tries to access the messages in question.
Devices should be double checked for lingering profiles / email account configurations - have their caches flushed if possible (powered off and restarted works wonders sometimes).
We gave up on Outlook mobile and have encouraged Thunderbird for mobile devices but that is out of the scope of your problems (and most likely not an option). SmarterMail recommends emClient across the board as an Outlook alternative. It might be worth testing at least on one device and see if emClient is having the same problems Outlook is.
Our company has run SmarterMail for 3 years give or take but we don't use the EAS/EWS/MAPI. In the end, logfiles set to their highest levels will be your friend in trying to track down the issue(s).
MailEnable survivor / convert --