Hallo dbrgn,
ich hatte aus meiner Sicht alle Tipps befolgt. Nachdem ich an anderer Stelle (allerdings nicht im Zusammenhang mit Threema) etwas Ähnliches bei den Samsung S8, S9, S10 und "Maximales Energiesparen" gelesen hatte, und die Lösung dort "App neu installieren" war, hab ich das in meiner Verzweiflung ausprobiert.
Also Backup etc gemacht, Threema deinstalliert, wieder installiert und prompt kamen die Nachrichten wieder zuverlässig an. 
Ich würde sagen Samsung hat mit seinem Energiemanagement was ordentlich verkackt...
