Hi,
Just recently started getting these errors messages that pop up all the time. And they all look fairly the same, but the website adress stated in them change, usually regpro.com, winc32clean.com , pcfixit.com etc. I've scanned with norton antivirus, Ad-awareSE, Spybot, Ewido anti-spyware and AVG Free. I'm running on windows 2000 professional.

This is one example of how these messages appear.

"Message from SECURITY to ALERT, sent 2006-09-03 20:15:36

Windows has found 55 immidiate threats.

STOP!
SCAN CRITICAL SYSTEM ERRORS

To fix the errors please do the following:
1. Download Regristry Repair from: http://www.regpro32.com
2. Install Regristry Repair
3. Run Regristry Repair
4. Reboot your computer
FAILURE TO ACT NOW MAY LEAD TO DATA LOSS AND CORRUPTION!"

The only thing you can do is press 'okay'. After scanning with all my anti-spyware/virus programs I've removed some tracking cookies and a few trojan horses, but these error messages keep popping up and I don't know how to fix it.

Any suggestions at all are welcome at this point.

That looks like it is coming from the Windows Messenger service. You can turn the Windows Messenger service off. Please see the following article - Disabling Messenger Service in Windows XP

I would also run the tools that you mentioned above from within safe mode. Before going into safe mode, make sure that all of the programs are updated.

You also mentioned that you ran both Norton antivirus and AVG. Having two antivirus programs running actively on your computer can cause problems. Please remove one of the antivirus programs to avoid conflicts. (I would remove Norton)

If you are still having problem, you can follow all the steps here before posting a HiJackThis log.

Once your system is totally clean, you should ensure that you have all Windows updates and patches installed.

Good-luck.