Apparently my Windows 7 x64 laptop is infected with something, it intercepts HTTP traffic and hijacks links to different websites to webplains.net, which then issues HTTP redirects to various websites that have presumably paid for this "service".
It works regardless of what browser is used, and it only seems to affect Google.com search results (so Bing has a use after all).
Some searching, especially for "webplains.net" suggests this may be the work of a known malware, TDSS, that can be removed with a one-off Kaspersky tool. I ran the tool, but it reported nothing out of the ordinary. Furthermore I can't find any tools that help with removing malware on 64-bit systems.
I don't really have anything to boot off to have a look at the filesystem. I can't see any malware in my current filesystem (of course, that's how rootkits work) - but I did find a malware file in my SysWow64 directory that has since been deactivated (it setup a Scheduled Task to rundll.exe itself on system startup).
My computer doesn't have an optical drive, so I'll have to boot from a USB stick, but I don't know what system is best for this. I have run the official WinPE in the past and I wasn't too impressed with it, but BartPE leaves a lot to be desired. Unfortunately the HDD in my laptop cannot be removed without breaking the warranty (as it involves the complete removal of the underside cover).