Bei mir laufen microG und Threema gut zusammen. Wichtig ist, dass bei der Installation und ersten Einrichtung von Threema microG schon korrekt eingerichtet ist. Ich kenne auch einige andere, bei denen das funktioniert.
Threema kann da denke ich aber noch nachlegen, da die App scheinbar nur bei der Einrichtung nach der FCM API schaut. Ich glaube, dass andere Apps auch zu späteren Zeitpunkten noch einmal nachschauen, ob es "mittlerweile" die FCM API gibt. Eventuell sinnvoll als Funktion in den Einstellungen, dass man Threema erneut nach der API suchen lässt.