Are you also using iCloud email on a Mac using the Mac email client? The settings in Mac Mail could be different than your iPhone settings for mail.
Read the fine print about the deletion and archiving preferences in various apps. Some store the "deleted" messages on your own system, which you pay for, and the ones who store the deletions on central servers have to worry about how to pay for the equipment. That can do that by charging you for it or by ensuring you never use more than a specified amount of their storage.
The prime directive of any business is to survive!
Take a look at this page in the Apple Mail User Guide on Support.apple.com. It starts out talking about settings to control where certain mailboxes are stored but then deals with settings about when when messages will be automatically deleted.I'm not sure how that helps me, but thank you for your reply.