Browser redirectors and hijackers typically manifest the symptoms the OP is describing, and can many times be gotten rid of fairly easily, i.e., removing toolbars, clearing cache, resetting browsers, flushing DNS, etc. Although some can be difficult, most of the time they can be gotten rid of without resorting to a clean install.