Da das Phänomen zum Einen Global zu sein schien und es zum Anderen keine Änderung im Traveler gegeben hatte, dachte ich schnell an die vielen Probleme, die das iOS 13 verursacht. Mit einer schnellen Recherche konnte ich bestätigen, dass dieses Problem keineswegs einmalig ist, sondern nicht wenige Nutzer mit iOS 13 betrifft. Unter Anderem konnte ich auf Spiceworks einen Tread finden, der dieses Problem behandelt.
Die Lösung: Das Problem scheint mit iOS 13 < 13.2.3 aufzutreten. Allerdings wird es auch wohl nicht durch ein einfaches Update auf 13.2.3 (oder jetzt 13.3) behoben, sondern das Mail-Konto muss wohl gelöscht und neu angelegt werden.