Where is contact sync off?
Please check both:
- Phone settings -> accounts -> tap into Aqua Mail's -> Mail, Calendar, Contacts - this one
- In Aqua Mail long press on the account -> options and folders -> Exchange options
Both are one and same setting (Aqua Mail reads and changes that system setting).
The only difference is that turning this setting off in Aqua Mail will delete any previously synced contacts -- while turning it off in Phone Settings will not.
Is contact sync still off in both places?
Are you perhaps creating contact entries under the Aqua Mail account, using anything, anything at all, such as the Contacts app, or saving a recipient into Contacts, anything anywhere?