The Hostsfile is definitely a good place to start. If that works, you're home free. It may not; hijackers sometimes hide files that effectively rebuild the main browser and search redirect files if the user is sharp enough to try to get rid of them. If not, both Spybot S&D and AdAware, with their current updates, should detect and defeat PerfectNav if run in safemode, though it wouldn't hurt to run CWSKiller and CoolWebShredder first. Links to, and instructions for, all of them may be found
HERE and also
HERE, where too you can find detailed instructions for detecting, removing, and preventing all sorts of yuckware.
If that doesn't work, and you feel comfortable enough to try this at your own risk, following (as found on several Security/Privacy forums and newsgroups) are manual PerfectNav removal instructions for XP; those for previous Windows versions should be similar enough that they can be figured out.
Start > Run > type "regedit" (w/out the quotes), click OK.
Navigate to the HKEY_LOCAL_MACHINE\SOFTWARE folder, open it, then look for and delete 'HKEY_LOCAL_MACHINE\SOFTWARE \ Classes \ CLSID \ {A045DC85-FC44-45be-8A50-E4F9C62C9A84}', if it exists, and 'HKEY_LOCAL_MACHINE\SOFTWARE \ Microsoft \ Windows \ CurrentVersion \ Explorer\Browser Helper Objects \ {A045DC85-FC44-45be-8A50-E4F9C62C9A84}', if it exists.
Be precise with this; delete only those exact keys, nothing else. If they do not exist, do nothing. Exit regedit and reboot into safemode.
Go to Start > Search > All files and folders, enter "perfectnav*" (without the quotes, but with the asterisk), set "Look In" to "My Computer", click "More advanced options", and select "Search System Folders", "Search Hidden Files and Folders", and "Search Subfolders". Be sure "Case Sensitive" is not checked. Then click "Search now". Delete everything found.
Open Internet Explorer. If prompted, select "Work off line", and don't be concerned if "Cannot display page" comes up; ignore it. From the Internet Explorer toolbar, select Tools > Intenet Options. On the first page, under the "General" tab, in the first panel, select "Use Blank" for Home Page. In the second panel, select "Delete cookies", click OK in the window that pops up to confirm you wish to delete them, then select "Delete files", choosing to delete "All offline content" when that option window opens, click "OK" to confirm you wish to delete. In the third panel, select "Clear History" and again confirm when prompted. Click "Apply" down at the bottom of the Internet Options page, but do not click OK yet; go instead to the second tab, "Security". Select "Default Level" and click 'OK" in the confirmation window that pops up, then click "Apply" at the bottom of the page. Next, go to the last tab, "Advanced", and select "Restore Defaults", confirm if prompted, and click "Apply" Now, go to the 5th tab, "Programs", and select "Reset Web Settings" confirm when prompted, and click "Apply". Then, move to the 3rd Tab, "Privacy", and set the slider to "Medium High", confirm you wish to change settings when prompted to do so, then click "Apply". Finally, click "OK" at the bottom of the Internet Options page to exit.
Now, empty your recycle bin. Reboot normally, connect to the internet, open Internet Explorer, navigate to your preferred home page, again go to the Internet Explorer toolbar, select Tools > Internet Options and, on the "General" Tab, in the first, or "Set Home Page" panel, select "Use Current". Click "Apply", then click "OK" to exit. That should be it.