Looks as if I picked up what seems to be the Google Redirect Virus after I had recently reformatted the computer (*makes a note to set up security straight after reformatting in the future*).
Tried and tested the 'solutions' found by simply searching via google (Looking for changes in browser connection settings, LAN settings, hosts file - scanning with Malwarebytes, Superantispyware, ESET Nod32 4), but to no avail.
As it occured straight after reformatting I had no problem with reformatting once again in an attempt to get rid of it, but I believe that since my laptop (Sony Vaio VGN NR11S/S) has an stored recovery partition (no CD required) it didn't help as the virus seems to have infected it.
I am running Windows Vista as my OS.
Only real issue is the links being redirected, desktop is still visible and folders appear to function normally, though the computer is acting a bit dodgy (e.g. had to do a system restore when it unexpectedly shut down and was unable to initiate windows, but it still worked in safe mode). Seeing as the internet settings and hosts file seemed to have been left untouched I am uncertain as to the nature of the virus beyond the redirecting issue.
Your help is much appreciated Let me know if you need any further info.
Edited by Heffadir, 12 July 2011 - 09:44 PM.