I keep getting a pop up message (actually 2 similiar mssg.) - it says Messenger Service in the top corner and in the box it says:

Message from Local System to user on (date & time)
CRITICAL ERROR MESSAGE! Registry Damaged & Corrupted
To fix this proplem:
Open IE & type www.registrycleanerxp.com
Once you load the web page, close this message window
After you install the cleaner program you will not receive any more reminders or popups like this. Visit www. registrycleaner.com immediately!

The other message says (same messenger service box)
Message from Registry to Cleaner
Stop! Registry Cleaner Recommended
To download & scan computer for registry error:
1. Visit www. registrycleaner.com
2. Download & install Registry Cleaner
3. Scan computer for any possible errors
4. Register to complete scan corrections
5. Registry cleaner can improve system performance & stability issues.

I get this pop up constantly (like every minute or two). I have re-formatted my hard drive & reinstalled my operating system and a minute after windows starts up, I get the pop up again. If I unplug my ethernet cord from my modem (I have comcast high speed internet), I don't get the message. I even plugged in a different computer to my modem and bam! it got the pop up too! I've tried anti-virus protection, firewall, spyware/adware scans nothing gets rid of it. Somebody please help me. I don't know what else to do!

Thank you in advance for any suggestions.