This is a bit hit and miss, but it could be a mistake to assume that the problem with your connection is directly related to the removal of the software. There could be a link, but don't be too hasty and don't discount other options. With a P2 it doesn't take much to bring a system to its knees.
I would begin with an online virus scan and malware scan.
Then I would thoroughly defrag the hard disk (removing two deeply embedded apps may have been the final straw).
You could delete the windows swap file, whish is usually missed by defragmenters (do it in DOS) - it will be re-created when you re-start windows.
If all else fails, you may have to re-build the OS from scratch. IF you do, use applications that are of the time your PC was build - office 95 instead of XP for example - to avoid bloating.
If you want a simple antivirus program which runs well on older systems, try Antivir Personal Edition (search Google). Don't worry too much about a firewall on a dial-up system, at least for now.
If you need help with any of these suggestions, post back.