消したはずのメールが出てくるどうすればいいのでしょうか？

iPhone のメールの話ですかね？

普通はimapという方式なので、メールは全部サーバ側で管理してます。また、メールを捨ててもいきなり消すのではなく、（間違って消してしまうのを防ぐため）、ゴミ箱みたいなフォルダーに移すだけです。だけどゴミ箱のメールは一定期間後（１ヶ月程度？サーバによって違う）には，自動で本当に消去されますので、気にしなくてよいです。

直ぐに消したいなら設定、メールから各アカウントを開いてメールの移動先をサーバーのゴミ箱にしましょう。そうすればサーバーのゴミ箱に入り削除したら完全に消えます。

gmail,Exchangeなんかはそのまま削除するとすべてのメールというところに入ってしまい、ゴミ扱いしないので消えないで残る場合が有ります。

パソコン等と一緒で一旦ゴミ箱フォルダに移動します

すぐに消したい場合はゴミ箱フォルダの中でもう一度削除してください。

完全に消去されます。