I hate system restore. Worthless in my book. I'll take a clean install any day. I disable the system restore service first thing on any XP machine I use.
However, you have multiple problems. You have a hardware issue, with this PCI error at boot... that need to be resolved first. A trojan aint gonna do that.
Second, I'd would set up Mcaffee to update every single day ("updated just the other day" is unacceptable - new stuff comes out every day) Then boot into SAFE MODE and run a full scan, twice.
Third, I would DL a copy of Adaware, and remove all spyware. Some of it it difficult to remove if you were careless and installed things based on popups.... that were misleading.
Keeping in mind, removing some trojans cripples the OS, and requires a re-install anyway.
Software firewalls add another level of protection beyond the simple firewall rules of a NAT router.... so if you tend to get infected with these things (lack of diligence) then they are good to have.... but a pain in the ass.
I have been running for years without a software firewall, without issue, but I keep my system clean, and use a quality AV (CA Etrust is my top choice, Norton second... I think McAffee sucks personally) and I have it check for updates every 4 hours, and run scheduled scans weekly.