I'm no computer expert, but I'd say formatting the harddisks and reinstalling the OS (although it surely will help), is not really needed.
Yes, the windows folder grows bigger and bigger and the system gets a tad slower over time, but I'm sure you can fix your problem without a complete reinstall.
For sure try reinstalling the game first. This alone could already solve your problem. Also, I'd get the lates directX and new graphic card drivers (I've Direct X ten, although my gfx card only supports DX9).
Also, do a defrag from time to time. Maybe disable your virus on demand scanner while playing, this saves resources and might increase performance.
If that all doesnt help, I'd agree with Judi, a fresh windows installation is in order.
BTW, you could also think about creating a new partition of your harddisk. Then install windows there as well, and you have a superfast new system without any crap that will slow it down. There you install WC3 and see if it works.