Ich weiß nicht wie das beim iPhone ist da ich kein habe.

Aber bei Android gehe ich nach Einstellungen/Apps/Verwalten suche da die Mailapp aus und kann den Cache dort leeren.