You probably have a porn dialer. These can get very expensive very quickly if you don't stop them before they connect. This little beasty most likely came from somebody clicking through an ActiveX warning or clicking on a banner ad. This article (http://experts.about.com/e/s/sp/Spyware.htm) provides a good overview of spyware and how to prevent and fight it.
If you already have antispyware software installed, it is most likely outdated or has been compromised. You will need to install new antispyware software.
[b]Note: You will not be able to download the software directly to the infected PC via dial-up.[/b] (I know you've already figured this out, but my conscience won't let me not say it. :| )
Find a PC that's directly connected to the internet, or even better, get the infected PC to a broadband connection. Download Spybot S&D from http://www.safer-networking.org/en/index.html and Spyware Blaster from http://www.javacoolsoftware.com/spywareblaster.html.
These two programs will take care of most spyware and both have good interfaces (fairly intuitive).
Install both programs (SpywareBlaster first) while you are still online and allow each to search for and install updates as part of the install routine.
After Spyware Blaster is installed and started, update, then select "Enable all protection."
In Spybot S&D, select the Immunize function and follow the procedure to immunize. Once you have immunized, start a scan. The scan should find the hijacker. After the scan, you can choose to fix the problem. If Spybot won't fix the problem, you will at least know the name of the culprit and be able to search for a fix.
If you are not already running Windows Defender, you may want to install it as well.
Peer me if this doesn't work or if you have any more questions. I can't guarantee a one-hour response, but can get back the same day.
Edit: clarify
