I didn't "just" divulge EWS. My OP says I'm using office365. There's no activesync support, is there?
Office365 can also be accessed via IMAP or POP3. (You can google that, see e.g.
https://www2.warwick.ac.uk/services/its/servicessupport/email/liveemail/faqs/popimap/ )
I'm syncing 30 days, 250 messages to cache (no idea what that means). I have the exact same settings in Touchdown - 9K, and in Nine (now testing) - 100K.
If you have 3500+ deleted messages over 30-day period, I wonder: how many messages do you have in your Inbox? If you have more than that, you might consider reducing that number.
If you really need some of the older messages, you can always keep scrolling, and the app will load additional messages.
Now, another issue is 250 messages to cache.
To understand what that setting does, read the FAQ item "Messages to sync and messages to cache settings"
http://www.aqua-mail.com/?page_id=227Normally, "messages to cache" is expected to be larger then "messages to sync".
I know that when they are the other way around, and "messages to sync" is set for the number of messages, Aquamail is smart enough to recognize this problem, and behaves correctly.
I am not sure if the same happens when "messages to sync" is set to the number of days, and that effectively exceeds the number of messages to cache. I wonder, if Aquamail might delete some messages from "cache", and that results in the necessity to re-download those messages next time. You'd have to wait until the developer, Kostya, will be back from his vacation (on Monday).
(I doubt that anybody else from MobiSystems [that/who "
puts great effort in developing, testing and supporting the app", would know the answer to that question.]
In the mean time, I'd seriously recommend reducing "messages to sync" to 1-2 weeks, and, probably increasing "messages to cache" to, say 500-1000.