i can't help in detail with the first part of your problem (having failed with that last time
), but last time i had to re-install windows 2k pro after mandrake, i used the mandrake control centre to write a copy of GRUB to a bootdisk. after windows over-wrote GRUB, i was able to use this to boot back into linux and use MCC to put GRUB back in its correct place!
i'm going to have to go through the same process as you myself soon, since 2k has destroyed itself. again. joy-oh-joy
hope this is of use to you anyway. good luck!
--matt