From the link Nepatsfan (congrats on 16-0, BTW!) and Ken gave:

"To replace Microsoft software that was distributed with your computer
by an OEM or a System Builder, contact the OEM or the System Builder
directly."

Years ago, I purchased a custom-built PC. I, too, lost my installation
disc. I contacted him, and he promptly mailed me a copy of a generic OEM
install disc, which  can be used with one's product key. If you don't
know your product key, you should be able to retrieve it by using Belarc
or Magical Jellybean Finder:

(1) http://www.belarc.com/free_download.html

(2) http://www.magicaljellybean.com/keyfinder.shtml

Once you have your key, write in down and stick it to your PC's case!

Hopefully, you will be able to obtain a generic OEM disc, too, without
having to purchase a brand new one. Although it's possible to download a
torrent, I can't recommend this method because there's no guarantee it
will be free of viruses, rootkits, etc. Instead, maybe you can find
someone (a co-worker, friend, relative, neighbor, etc.) who has one.
Then you can make a copy.

Worst case scenario is that you will need to purchase another
installation disk, which should cost under $100. But let this be a last
resort.

Although the most certain method of cleaning a thoroughly compromised
system is to perform a clean install, you first may want to try
something less drastic. The many things you tried certainly haven't
worked yet, so let's start from scratch:

Malke's page has a lot of useful information:

http://www.elephantboycomputers.com/page2.html#Viruses_Malware

Basically, you need to address viruses, worms, trojans, etc. *and*
non-viral malware (spyware, etc.) I know you already know this, but
since your methods (which you didn't disclose) haven't yielded
satisfactory results, I'm mentioning it.

For the first part of the equation, many people have had success with
David Lipman's Multi AV Scanning Tool:

http://www.pctipp.ch/downloads/sicherheit/35905/multi_av_scanning_tool.html

Although the page is in German, the tool is in English.

Personally, I've been very happy with AVG Free:

http://free.grisoft.com/doc/2/

Others have reported that Avast is a very good antivirus app:

http://www.avast.com/eng/avast_4_home.html

(By the way, all the links I'm giving you are for freeware.)

And for spyware, there are many fans of SUPERAntiSpyware Free:

http://www.superantispyware.com/superantispywarefreevspro.html

Personally, I use Ad-Aware and Spybot Search & Destroy to handle
spyware:

http://www.lavasoftusa.com/products/ad_aware_free.php

http://www.safer-networking.org/en/spybotsd/index.html

If you're interested in *preventing* spyware from entering your PC,
SpywareBlaster is a good app:

http://www.javacoolsoftware.com/spywareblaster.html

One final suggestion is to run HijackThis (if you think you may still
have more malware). Download it from:

http://www.spywareinfo.com/~merijn/programs.php

and post the log to an appropriate forum, such as:

http://www.bleepingcomputer.com/forums/forum22.html

Here's a helpful tutorial:

http://www.bleepingcomputer.com/tutorials/tutorial42.html

Once you are satisfied that you are malware-free, there are other steps
you can take to speed up your PC. First of all,  you need to determine
if  you have enough RAM for how you use your PC. Press Ctrl+Alt+Del to
open Task Manager. Click on the Performance tab.
Look under Commit Charge (K) in the lower left-hand corner. What are the
values for Total, Limit, and Peak? Also, how much RAM *do* you have?

If you don't have enough memory, you will find Windows will start using
the pagefile frequently, which slows everything down.

Last suggestion:

Take out the trash (clear temp files) and defrag the hard drive if you
haven't done so already. There are a few different ways to clear away
temp files from within Windows (Disk Cleanup, for instance). I
personally like Ccleaner, which has a very user-friendly interface:

http://www.ccleaner.com/

Just use the main feature of cleaning temp files. Don't use the Issues
feature (not necessary and it's possible it might mess things up!).

Good luck!

Then you are either using poor-quality security software, not keeping
them up-to-date, not practicing safe hex, or all three.

If you do that without finding out what the problems are, and what
caused them, you will undoubtedly repeat the behavior that caused the
problems and quickly find yourself back in the same situation. I am
hardly ever in favor of doing this, but it's your choice of course.

Regarding your application software, whether you can get replacements
depends on what the software is and who manufactured it.

Regarding Windows, whether you can get a replacement or not depends on
whether it's OEM or not. Reread what I posted in an earlier message in
this thread:

If your copy of Windows is an OEM version (computers that come with
Windows pre-installed have OEM versions, but also some people buy and
install OEM versions themselves), Microsoft will not help you. You
need to contact the OEM to find out how to reinstall, or to buy a CD
from them.

But if it's a retail CD, contact Microsoft. You may be able to get a
replacement CD at a nominal cost. Look here:
http://support.microsoft.com/kb/326246/en-us

You were answered - twice - with the proper answer before you wrote this
additional response...
"frustrated' or not - you should read the answers people give you in full.
;-)

How to replace Microsoft software or hardware, order service packs and
product
upgrades, or replace product manuals
http://support.microsoft.com/kb/326246

You will need proof of purchase.

Beyond that - given what you have - if you can find somoeone with the same
type (GenericOEM or RETAIL - depending on what you bought) Windows XP CD,
you can copy/utilize it.  Don't know which you bought?  Think back to how
much it cost.  Since you say Windows XP Professional; $199+ - Likely Retail.
Less than that for the OS?  Likely OEM.