Stop using the hd.
Install a fresh copy of win or linux on pc.
Hook up old hd.
Run recovery file software on old hd.
Pray.
Definitely agree with step #1 above.
It's possible you might be able to recover your key(s) by just searching the block device (/dev/sda probably though it will be something else if you mount it on a different machine). Unfortunately, there is no easily recognizable header on the wallet.dat file which complicates things. There are some recognizable strings you might be able to search on.
If you have actually written over the piece of disk the wallet was on, you're about out of luck. Though you could get lucky and run across a piece of the Windows swap file that contains the key or an old copy that was marked as deleted.
How many bitcoins are you talking?