May be similar to your problem.
I found I couldn't delete some e-mails from my iphone although they happily deleted on my ipad.
Eventually solved the problem by deleting my email account on iphone, hard turned iphone off and on, re-installed my account checking that the boxes mirrored my ipad account.
The emails did not reappear.
Googling the problem indicates it maybe something to do with imap emails being held on my isp's srver.