Mail will not stay in trash
I had this issue and found quite a few solutions, from adjusting the settings in the mail app, reviewing the server settings up to deleting the email account altogether from my iphone. I tried and reviewed all (except for the removing of the email account) and came to a solution which worked for me:

1 - went to the account settings that was giving me the issue and changed the "Sync" period to 1 day.
(Settings / Mail / Accounts / &lt;email account&gt; / Sync Mail)

2 - get our of the settings and open the mail app. Wait for it to sync, once the account is synced, the emails you wished to be removed will still be there, but just delete them (again).

3 - you will still receive the "message could not be moved to the trash" notification, however, the messages will not return to your inbox (as they did previously).

4 - wait a couple of days to go back to your settings and change the sync period to whatever you like.

This worked for me and I believe it should work for anybody which the previous solutions did not work with.

For me I believe it was an issue when I deleted the emails both from the server and the iphone mail client when it (the iphone) was not connected to the internet.

Anyway I hope this helps!