Since upgrading to iCloud I am not able to delete messages in mail on the iPhone or on the Mac. If i delete a message it comes right back. I can delete it on iCloud.com though. How can i fix this?
I also had exactly the same issue.
Checked all my setting in mail - all OK.
Then remembered seeing a new iCloud icon in System Preferences.
Under iCloud - Mail & Notes were not ticked!
Once I ticked this a new iCloud mailbox appeared and all worked fine.
Hope this works for you!!