Da nach dem Löschen diverser Caches und Logfiles, deaktivieren des vnc-servers (der in der Tat auf dem Pi-Hole nutzlos war)
sowie dem flushen der Iptables, keinerlei Besserung in Sicht war,
setzte ich ein neues Pihole auf einer anderen, neuen SD-Karte auf (selbe Größe, 16GB Class 10).
Erstaunlicherweise war nach diesem Vorgang das Problem nicht behoben. Ein weiterer Rechner,
sowie mein Smartphone (via WIFI) haben die selben Probleme.

Ich teste in den nächsten Tagen mal einen Rechner der nicht den PiHole als Nameserver nutzt.