I haven't tried Push for Exchange (so, I haven't used the newest version myself), - but if the configuration interface is similar to that for IMAP Push, there are actually three (3!) places where you need to enable Push:
1. Overall app level settings (3-dot menu from the account view )
2. Account settings (long press on the account in the account view -> options and folders)
3. Inbox (folder properties)
From your description, I suspect (2) might not be enabled.
You haven't mentioned what you phone model and Android version is.
While I don't know all the details of the Exchange Push implementation, but I think it might still be subject to the problem cause by "battery optimization". "Battery optimization" can be happening (a) at the Android level (6.0+) - so called "Doze" mode, (b) specific OEM extension (e.g. Samsung, Huawei, etc...), or (c) a 3rd-party application. In all three cases, you need to add Aquamail to the whitelist to exclude from "being optimized". That optimization simply disables apps from working.
See the FAQ item "Persistent network errors or the app not checking mail, MIUI, Huawei" in the Aquamail FAQ
http://www.aqua-mail.com/?page_id=227