Most links redirecting to ads

So, this problem appeared a few days ago - firstly windows started alerting me that an application I didn't recognise was crashing every 5 minutes. A quick check and it turned out to be a (Pretty poorly coded if you ask me) trojan which kept crashing. MBAM swiftly removed it, however I've noticed that since then links keep redirecting me to ad sites and sometimes a new tab will just show up (Every site they've so far redirected to has either already been in, or I've immediately added the domain to my adblock definitions).

My browser is Firefox (3.6.15) I reinstalled the latest version and the problem remains.

I've checked my extensions for known advertising bots, but no sign of any. The only ones in there are my standard ones I personally installed, like adblock.

So far I've done full system scans with the following tools:

MBAM
AVG
Spybot S&D
Microsoft Malicious software remover

All are fully updated to the latest version, all say my system is 100% clean.

I checked the HjT log myself but couldn't find any entries normally associated with this problem, anyone else care to see what I may have missed?

(As a side note, when I removed the trojan, my system restore history was deleted as an added precaution - which led to my woes yesterday with an infinite loop of bluescreens, caused by the kernel not liking something zonealarm had left behind when it was uninstalled)

Code:

 
Logfile of Trend Micro HijackThis v2.0.4
Scan saved at 08:44:05, on 18/03/2011
Platform: Windows 7 (WinNT 6.00.3504)
MSIE: Internet Explorer v8.00 (8.00.7600.16385)
Boot mode: Normal
 
Running processes:
C:\Program Files (x86)\Ray Adams\ATI Tray Tools\atitray.exe (Before you say anything - I need this to make my second monitor visible. It's too dark without the individual gamma boost this allows me to implement)
C:\Program Files (x86)\Common Files\Java\Java Update\jusched.exe
C:\Program Files (x86)\Common Files\Adobe\ARM\1.0\AdobeARM.exe
C:\Program Files (x86)\Citrix\ICA Client\concentr.exe
C:\Program Files (x86)\AVG\AVG10\avgtray.exe
C:\Program Files (x86)\Citrix\ICA Client\wfcrun32.exe
C:\Program Files (x86)\DisplayFusion\DisplayFusionHookx86.exe
C:\Program Files (x86)\Common Files\Java\Java Update\jucheck.exe
C:\Program Files (x86)\Online Armor\OAhlp.exe
C:\Program Files (x86)\Mozilla Firefox\firefox.exe
C:\Program Files (x86)\Mozilla Firefox\firefox.exe
C:\Program Files (x86)\Mozilla Firefox\plugin-container.exe
C:\Program Files (x86)\Trend Micro\HiJackThis\HiJackThis.exe
 
R1 - HKLM\Software\Microsoft\Internet Explorer\Main,Default_Page_URL = MSN.com
R1 - HKLM\Software\Microsoft\Internet Explorer\Main,Default_Search_URL = Bing
R1 - HKLM\Software\Microsoft\Internet Explorer\Main,Search Page = Bing
R0 - HKLM\Software\Microsoft\Internet Explorer\Main,Start Page = MSN.com
R0 - HKLM\Software\Microsoft\Internet Explorer\Search,SearchAssistant = 
R0 - HKLM\Software\Microsoft\Internet Explorer\Search,CustomizeSearch = 
R0 - HKLM\Software\Microsoft\Internet Explorer\Main,Local Page = C:\Windows\SysWOW64\blank.htm
R0 - HKCU\Software\Microsoft\Internet Explorer\Toolbar,LinksFolderName = 
F2 - REG:system.ini: UserInit=userinit.exe,
O2 - BHO: AcroIEHelperStub - {18DF081C-E8AD-4283-A596-FA578C2EBDC3} - C:\Program Files (x86)\Common Files\Adobe\Acrobat\ActiveX\AcroIEHelperShim.dll
O2 - BHO: Windows Live Sign-in Helper - {9030D464-4C02-4ABF-8ECC-5164760863C6} - C:\Program Files (x86)\Common Files\Microsoft Shared\Windows Live\WindowsLiveLogin.dll
O2 - BHO: Java(tm) Plug-In 2 SSV Helper - {DBC80044-A445-435b-BC74-9C25C1C588A9} - C:\Program Files (x86)\Java\jre6\bin\jp2ssv.dll
O4 - HKLM\..\Run: [HDAudDeck] C:\Program Files (x86)\VIA\VIAudioi\VDeck\VDeck.exe -r
O4 - HKLM\..\Run: [SunJavaUpdateSched] "C:\Program Files (x86)\Common Files\Java\Java Update\jusched.exe"
O4 - HKLM\..\Run: [Adobe Reader Speed Launcher] "C:\Program Files (x86)\Adobe\Reader 9.0\Reader\Reader_sl.exe"
O4 - HKLM\..\Run: [Adobe ARM] "C:\Program Files (x86)\Common Files\Adobe\ARM\1.0\AdobeARM.exe"
O4 - HKLM\..\Run: [ConnectionCenter] "C:\Program Files (x86)\Citrix\ICA Client\concentr.exe" /startup
O4 - HKLM\..\Run: [StartCCC] "C:\Program Files (x86)\ATI Technologies\ATI.ACE\Core-Static\CLIStart.exe" MSRun
O4 - HKLM\..\Run: [AVG_TRAY] C:\Program Files (x86)\AVG\AVG10\avgtray.exe
O4 - HKCU\..\Run: [DisplayFusion] "C:\Program Files (x86)\DisplayFusion\DisplayFusion.exe"
O4 - HKCU\..\Run: [AtiTrayTools] "C:\Program Files (x86)\Ray Adams\ATI Tray Tools\atitray.exe"
O4 - HKCU\..\Run: [Google Update] "C:\Users\Washu\AppData\Local\Google\Update\GoogleUpdate.exe" /c
O4 - HKUS\S-1-5-19\..\Run: [Sidebar] %ProgramFiles%\Windows Sidebar\Sidebar.exe /autoRun (User 'LOCAL SERVICE')
O4 - HKUS\S-1-5-19\..\RunOnce: [mctadmin] C:\Windows\System32\mctadmin.exe (User 'LOCAL SERVICE')
O4 - HKUS\S-1-5-20\..\Run: [Sidebar] %ProgramFiles%\Windows Sidebar\Sidebar.exe /autoRun (User 'NETWORK SERVICE')
O4 - HKUS\S-1-5-20\..\RunOnce: [mctadmin] C:\Windows\System32\mctadmin.exe (User 'NETWORK SERVICE')
O4 - Global Startup: desktop (1).ini
O10 - Unknown file in Winsock LSP: c:\windows\system32\msible.dll
O16 - DPF: {E2883E8F-472F-4FB0-9522-AC9BF37916A7} - http://platformdl.adobe.com/NOS/getPlusPlus/1.6/gp.cab
O17 - HKLM\System\CCS\Services\Tcpip\..\{5A64CC60-EF60-4539-87A6-9125570B5318}: NameServer = 194.168.4.100,194.168.8.100
O18 - Filter: application/x-ica - {CFB6322E-CC85-4d1b-82C7-893888A236BC} - C:\Program Files (x86)\Citrix\ICA Client\IcaMimeFilter.dll
O18 - Filter hijack: ica - {CFB6322E-CC85-4d1b-82C7-893888A236BC} - C:\Program Files (x86)\Citrix\ICA Client\IcaMimeFilter.dll
O23 - Service: @%SystemRoot%\system32\Alg.exe,-112 (ALG) - Unknown owner - C:\Windows\System32\alg.exe (file missing)
O23 - Service: AMD External Events Utility - Unknown owner - C:\Windows\system32\atiesrxx.exe (file missing)
O23 - Service: AVG WatchDog (avgwd) - AVG Technologies CZ, s.r.o. - C:\Program Files (x86)\AVG\AVG10\avgwdsvc.exe
O23 - Service: @%SystemRoot%\system32\efssvc.dll,-100 (EFS) - Unknown owner - C:\Windows\System32\lsass.exe (file missing)
O23 - Service: @%systemroot%\system32\fxsresm.dll,-118 (Fax) - Unknown owner - C:\Windows\system32\fxssvc.exe (file missing)
O23 - Service: @keyiso.dll,-100 (KeyIso) - Unknown owner - C:\Windows\system32\lsass.exe (file missing)
O23 - Service: @comres.dll,-2797 (MSDTC) - Unknown owner - C:\Windows\System32\msdtc.exe (file missing)
O23 - Service: @%SystemRoot%\System32\netlogon.dll,-102 (Netlogon) - Unknown owner - C:\Windows\system32\lsass.exe (file missing)
O23 - Service: Online Armor Helper Service (OAcat) - Unknown owner - C:\Program Files (x86)\Online Armor\OAcat.exe
O23 - Service: @%systemroot%\system32\psbase.dll,-300 (ProtectedStorage) - Unknown owner - C:\Windows\system32\lsass.exe (file missing)
O23 - Service: @%systemroot%\system32\Locator.exe,-2 (RpcLocator) - Unknown owner - C:\Windows\system32\locator.exe (file missing)
O23 - Service: @%SystemRoot%\system32\samsrv.dll,-1 (SamSs) - Unknown owner - C:\Windows\system32\lsass.exe (file missing)
O23 - Service: @%SystemRoot%\system32\snmptrap.exe,-3 (SNMPTRAP) - Unknown owner - C:\Windows\System32\snmptrap.exe (file missing)
O23 - Service: @%systemroot%\system32\spoolsv.exe,-1 (Spooler) - Unknown owner - C:\Windows\System32\spoolsv.exe (file missing)
O23 - Service: @%SystemRoot%\system32\sppsvc.exe,-101 (sppsvc) - Unknown owner - C:\Windows\system32\sppsvc.exe (file missing)
O23 - Service: Steam Client Service - Valve Corporation - C:\Program Files (x86)\Common Files\Steam\SteamService.exe
O23 - Service: Online Armor (SvcOnlineArmor) - Unknown owner - C:\Program Files (x86)\Online Armor\oasrv.exe
O23 - Service: @%SystemRoot%\system32\ui0detect.exe,-101 (UI0Detect) - Unknown owner - C:\Windows\system32\UI0Detect.exe (file missing)
O23 - Service: @%SystemRoot%\system32\vaultsvc.dll,-1003 (VaultSvc) - Unknown owner - C:\Windows\system32\lsass.exe (file missing)
O23 - Service: @%SystemRoot%\system32\vds.exe,-100 (vds) - Unknown owner - C:\Windows\System32\vds.exe (file missing)
O23 - Service: @%systemroot%\system32\vssvc.exe,-102 (VSS) - Unknown owner - C:\Windows\system32\vssvc.exe (file missing)
O23 - Service: @%SystemRoot%\system32\Wat\WatUX.exe,-601 (WatAdminSvc) - Unknown owner - C:\Windows\system32\Wat\WatAdminSvc.exe (file missing)
O23 - Service: @%systemroot%\system32\wbengine.exe,-104 (wbengine) - Unknown owner - C:\Windows\system32\wbengine.exe (file missing)
O23 - Service: @%Systemroot%\system32\wbem\wmiapsrv.exe,-110 (wmiApSrv) - Unknown owner - C:\Windows\system32\wbem\WmiApSrv.exe (file missing)
O23 - Service: @%PROGRAMFILES%\Windows Media Player\wmpnetwk.exe,-101 (WMPNetworkSvc) - Unknown owner - C:\Program Files (x86)\Windows Media Player\wmpnetwk.exe (file missing)
O24 - Desktop Component 0: (no name) - C:\Users\Washu\Desktop\stuffses\00_ayria-flicker-2005-back-fwyh.jpg
O24 - Desktop Component 1: (no name) - C:\Users\Washu\Desktop\stuffses\00_ayria-flicker-2005-front-fwyh.jpg
 
--
End of file - 7661 bytes

Hosts file was one of the first things I checked. Only the clean defaults for ipv4 and ipv6 are there. As for my ip configuration - for the LAN connection it's still set to the manual ip settings I set up for my network, for the internet one it's still on automatic, with my DNS set to Virgin's one (194.168.4.100).

Sorry, should have mentioned this in my original post. Only remembered to on my way to university. (Currently sitting in the reception on my laptop so any new suggestions will have to wait until I finish digesting this DNA and checking it for the gene I inserted)

Odd, you didn't see my edit clarifying it even though it was 10 minutes before you posted your reply? (That said, I have auto reload every 5 mins enabled on firefox here and your response only just popped up - might be the fault of the choppy network I have here at Uni) - My LAN settings are all manual ip (192.168.0.1, obviously), my net settings have manual DNS, and automatic ip.

As for your second question - No, I only use Microsoft Firefox Download Tool once, when I first install Windows. :P

What? Virgin's DNS might be what's hijacked?
Well, as soon as I get home I'll try those ones out, see if we can rule out that, and let you know what happens.

For now I have an agarose gel to run, so I expect to be done by 2pm.

*Edit* Actually I can rule that out already, since every other system on my network has exactly the same DNS settings. And they are all fine.

I've confirmed FF, IE and Chrome are all affected, confirming a more systemic problem.
And yeah, I'll make that DNS switch ASAP.