Recently, I've been working on two computers, where all Firefox searches were getting redirected.
Apparently, IE is not affected.
Both computers were checked through Superantispyware, Malwarebytes, Smitfraud tool, and AVZ.
Whatever infections was there, got removed (it wasn't much).
I thoroughly checked HJT LOG, and all Autoruns entires.
Totally nothing suspicious was there.
I was going nuts.
Redirection was still there.
Making a long story SHORT, this is what I discovered.
There is really nasty JavaScript worm out there: http://arstechnica.com/business/news/2008/01/javascript-worm-still-spreading-infection-origin-unknown.ars
Starting with ver. 6 update 10, Java automatically installs (UNLESS you opt out) Java Quick Starter Firefox add-on.
Once Java Quick Starter is DISABLED, and Firefox restarted, redirection is gone.
Apparently, Java Quick Starter is prone to the above worm.

Said that, I'd strongly recommend, everyone uninstalls Java Quick Starter.
To do so....
Go to Control Panel, double click Java. In the Java control panel, click the Advanced tab. Click the + sign in front of Miscellaneous and uncheck the Java Quick Starter box to remove the add-on.
Google the search term google.goored.com

This has been around since at least December and there is a custom tool for fixing it.

Quote

Java Quick Starter (JQS)

JQS is enabled by default in Windows XP and Windows 2000 operating systems and is not necessary on Windows Vista as Vista offers its own pre-loading mechanisms. A process called jqs.exe will run in the background in order to allow quick statup. jqs.exe will be loaded after a Windows restart. Instructions on how to disable the JQS and the jqs.exe process are below.

http://java.com/en/download/help/quickstarter.xml

Thanks evil. I found that fix, GooredFix