Ich denke (vorsichtiger Optimismus ☺), ich habe die Lösung gefunden:
Das Problem hängt zusammen mit der Option "Have the file manager handle the desktop" im gnome tweak. Ist diese Option aktiviert, laufen verschiedene Prozesse extrem verlangsamt ab. Einer davon scheint der Autostart von Mailnag zu sein.
Warum? Keine Ahnung. Aber seitdem ich die Option deaktiviert habe, funktioniert es (bisher) zuverlässig.