Podle mě záleží, jak je nastaveno to mazání na zařízení, odkud se mazalo - v nastavení IMAPu se dá nastavit, aby se mail na serveru buď hned smazal anebo se jen označil pro smazání, ale k jeho úplnému smazání aby došlo až časem (kdy, to je záleží také na nastavení).
Další možnost je, že server může při smazání mail sám přesunout do koše. Není to zrovna případ gmailu? Pohladal bych ten mail přes webové rozhraní gmailu, zda tam není třeba v koši. Tohle chování se tam dá tuším také nastavit, tentokrát v účtu gmailu (neověřeno).
No a nakonec v tom druhém zařízení, kde je ten mail stažený, je možno v offline režimu ten mail překopírovat do jiné složky, pak se připojit a synchronizovat, případně ten mail zase zkopírovat zpátky do původní složky, pokud by v původní složky zmizel a nová složka se na server nepřenesla nebo nezesynchronizovala (záleží na nastavení té složky a době vytvoření).
Poslední možností je si ten mail v offline režimu přeposlat, tím se překopíruje do odchozí pošty a při přepnutí do online režimu se pak odešle.
Jinak v offline i online režimu lze v závislosti na použitém klientovi celý mail uložit jako eml soubor (bude obsahovat všechny přílohy a lze jej pak kdykoli zase v jiném poštovním programu otevřít, dokonce aniž by v něm musel být nastavený jakýkoli poštovní účet). Určitě to umí třeba Thunderbird, ostatní poštovní klienti to budou mít podobně, nejhůř na tom budou asi poštovní klienti pro mobilní zařízení, tam hodně záleží, který program zrovna používáte.