Why did you find it necessary to format & reinstall Windows? You didn't do
a Repair Install, did you?
Is an anti-virus application installed and is your subscription current?
Was the Windows Firewall or a third-party firewall enabled immediately after
reinstalling?
How long have you been running, since the reinstall, without any Windows
Updates installed? Get the machine fully patched at Windows Update (do NOT
install IE7 yet!), make sure Automatic Updates is enabled, then tell us if
this behavior persists.
PS: To get the machine fully patched successfully, I think you're going to
need the following KB article:
http://support.microsoft.com/kb/943144