Yes I would format because I can back everything up on my secondary HD. Win98 takes 30mins too.
Yes last time I reformatted because for absolutely no reason, some websites I KNEW were up, would not work on this computer, but were fine on my other machine (on same connection).
Even with firewall off it does the same, I only have Zone Alarm.
After I reformatted it was all fixed.