Trojaner-Board - Verdacht: WLAN-Betreiber verfälscht Google Ergebnisse + DNSChanger gefunden

Hi,
ich nutze bei der Bundeswehr das öffentliche WLAN in unserem Mannschaftsheim und letztens ist mir etwas komisches aufgefallen.
Google Ergebnisse wurden auf einmal umgeleitet(z.B. bin ich statt auf die gewünschte wikipedia-Seite aus speeddownloading.com gelangt) und in Firefox ständig in einem neuen Tab geöffnet.

Ich konnte mir das nicht erklären und hab dann recherchiert, hab Hijackthis durchlaufen lassen und andere Programme wie Malewarebytes' Anti-Maleware.
Stand war immer das mysteriöse Registry-Einträge gefunden wurden die auf einen DNS-Changer schließen ließen.
Da ich kein verantwortliches Programm, Autostarteintrag oder Dienst oder ähnliches finden konnte habe ich meinen Rechner samt aller Festplatten formatiert.

Kaum hatte ich dann meinen PC (inkl. Antivir und ZoneAlarm, XP SP3) wieder im WLAN war das Problem wieder da.
Nun habe ich gerade die Einträge aus der Registry gelöscht, meinen Rechner neugestartet und via Handy mit dem Internet verbunden und siehe da, es war alles Ok.
Dann habe ich wieder das WLAN eingeschaltet und schwupps, es wurde wieder umgeleitet.
Als ich bei einem anderen Kameraden am Rechner nachschaute sah ich das er das Selbe Phänomen mit Firefox auf seinem Rechner hatte, ein Dritter z.B. mit Safari auch.

Meine Frage ist nun ob es möglich ist, das der WLAN-Betreiber das WLAN manipuliert oder von irgend jemand manipuliert wurde.
Die umgeleiteten Ergebnisse werden zwar korrekt angezeit (Suche mit "Trojaner Board") z.b. "http://www.trojaner-board.de/", werden aber auf:
"http://www.google.de/click?sa=T&ct=res&cd=1&url=http%3A%2F%2Fwww.trojaner-board.de%2F&q=trojaner+board&pid=0&u="
umgeleitet.
In diesem Fall komme ich zwar auf diese Seite aber manchmal ist der Link noch länger und enthält mehr Parameter wodurch ich auf andere Seiten gelange.
Den anderen Fall habe ich gerade mit der Suche nach "gratis bla" erzeugt.
Ergebnis eigentlich auf:
"http://www.hispanosnet.com/celulares/ringtones_gratis/los_simpson/bla_bla_ringtones_gratis.html"
Tatsächlich aber über:
"http://www.google.de/click?sa=T&ct=res&cd=1&url=http%3A%2F%2Fwww.hispanosnet.com%2Fcelulares%2Fringtones_gratis%2Flos_simpson%2Fbla_bla_ringtones_gratis.html&q=gratis+bla& pid=0&u=aHR0cDovLzcyLjIzMy4xMTguNzAvcC9pbmRleC5waHA/UEhQU0VTU0lEPWU1NTg0ZTg1MDIxOTY0MGE2Y2M3ZThhOGZkMDBjMzNmNjhmY2JhZmZhOGNhMDFiZTE4MzExM2Y2OWZkNTIwNDk4NDU0ZTQzOGRmM2QwZWIyNmUzNzIzZGIyYjA0YjVkNDkzODc3Yj A0YTMxYTFkYzhiMGZkM2Q4NTg5OTNlNzc3YWZlMWFlNjQxN2YzNGI="
auf:
"http://www.blau.de/app?service=direct/1/AirstripPage/dispatchLink&configId=4F404EDC2AB45CA7F14D26605A24DB0E4E2411FD&OVRAW=gratis%20bla&OVKEY=bla&OVMTC=advanced&OVADID=9172698031&OVKWID=44815463031"

Die Registryeinträge sehen wie folgt aus (Auszug aus Malewarebytes Log):
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Tcpip\Parameters\Interfaces\{b10ca978-a55f-4215-a33b-abed91846687}\DhcpNameServer (Trojan.DNSChanger) -> Data: 85.255.115.29 85.255.112.170 -> Quarantined and deleted successfully.
HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Services\Tcpip\Parameters\Interfaces\{b10ca978-a55f-4215-a33b-abed91846687}\DhcpNameServer (Trojan.DNSChanger) -> Data: 85.255.115.29 85.255.112.170 -> Quarantined and deleted successfully.

Soviel also zu meinem Problem und meiner Theorie.
Wäre gut wenn ich hier Hilfe finden würde.

Gruß UnD3Rd0g