I have an @icloud.com account, and:
- Sent three messages from my Gmail account: one from Aqua, one from Gmail / web, one from Gmail / Android
- All three appeared in the Sent folder in Gmail / web
- Message sent from Aqua appeared on the iPhone and iCloud / web about five minutes later
- Messages sent from Gmail / web and Gmail / Android still haven't made it to iPhone or iCloud / web twenty minutes one hour two hours later
- Sent two test messages from a different mail account (@Yandex.ru), one from Aqua, one from web mail
- Both made it to the iPhone and iCloud / web within seconds
Looks like there is an issue, but it does not look exclusive to Aqua, but rather related to Gmail and iCloud
Yes, I did see what you wrote about Outlook, but the above is what I saw.
Specifically for Aqua: please try long pressing the account -> options and folders -> composing and sending -> turn off "Send Message-ID header" at the end of the list.