Kleines Update von mir.
Ich habe auch nochmal nach Hilfe im Pi-hole Forum gesucht. Dort wurde mir bestätigt, dass das ganze Thema nichts mit Pi-hole zutun hat.
Ich habe also weiter gesucht und mir ist eine Sache immer wieder aufgefallen. Wenn mein DNS-Dienst eine IPv6 meiner FritzBox zurückliefert, tritt das beschriebene Problem auf. Wenn eine IPv4 zurück kommt, funktioniert alles wunderbar. Das Problem liegt also irgendwo auf FritzBox-Seite. Ich kann das beliebig oft nachstellen indem ich IPv6 im DNS entferne bzw. wieder hinzufüge.
Ich bin nur leider nicht dazu gekommen mit weiter um das Problem zu kümmern. Aktuell läuft alles 'nur' mit IPv6. Ich werde versuchen demnächst ein FritzBox-Forum zu finden und dort um Hilfe zu bitten.