The first thing you should do after installing a fresh operating system and before connecting to the internet is install the most recent service pack (SP1 for XP), a decent firewall (such as ZoneAlarm or McAfee Firewall), and a good anti-virus program with updated definitions. Once you have done this, then connect to the internet and proceed directly to windowsupdate.com to download all of the critical updates.
If you haven't done something like this, then you could possibly have contracted a worm/virus after you re-installed your OS.
Something else to check into is a bad driver for some of your hardware. I would recommend visiting the website for each of companies that have hardware inside your machine (video, network, modem, etc). I think you already mentioned you updated your BIOS to the latest version, if not, make sure to do this.
Also, you may want to see what all programs are automatically starting when your computer starts up. Check the "Startup" folder under your start menu. Also, do you have a ton of things showing up down by the clock in the system tray?
Not sure I've helped any, but maybe I got lucky somewhere in there.
Good luck with your problems. I recently upgraded to a newer version of McAfee anti-virus on my work computer and now my Outlook freezes up all the time. Ya gotta love these damn things.
