A few things...
You are correct that AquaMail does not have a problem, if you set it correctly. It has several deletion options. Actually, I don't see the deletion thing as a problem, more a different way of handling. I prefer a different way and with Android we have choices.
The term you are looking for is usually called 'expunge'. AquaMail has expunge options also. I used Mutt for many years, and if I remember right you're correct it is called 'autopurge' in Mutt. A little more self-explanitory term I guess.
Since Lollipop 5.0 the stock Android email app is the Gmail app and the only one by Google that's included. Any other email client on a device is either supplied by the manufacturer or a 3rd-party client.
Now, the Gmail app does things the way it does for whatever reason, and probably Google would like you to use the Gmail app. But trying to herd users into using it for 'spying' purposes isn't one of them. The Gmail app itself does nothing to help Google in their quest for your info. .It communicates directly with mail servers and mail is sent/recieved directly to/from servers without passing through Google.
IOW, email from non-Gmail accounts goes only through whatever servers are set. If it's not a Gmail account or an account purposely setup to go through Gmail, it never goes through Gmail servers and Google doesn't get a look at it. In this respect, unlike many other clients, the Gmail app behaves as it should.
Now, if you're using Inbox by Google instead of the standard Gmail client, it's a whole different story. Inbox is, like many clients now, cloud-based, meaning ALL email is run through and stored on Google servers, which in turn means they can - and no doubt do - scan ALL your email.
Email on iOS, as far as I can tell, works similar to Gmail. The default handling of deleted email is different. But why anyone would consider Applemail more secure than Gmail is a mystery to me.
See this:
http://androidforums.com/index.php?posts/7051405