To organize a relatively quick recovery, you should re-install Windows. Use an OEM copy of Windows, or if your computer has a official Windows product key on it, you should be able to get replacement discs from the vendor. I am surprised that they won't supply you with recovery media. If not, though, ask them for your CD. Insert the CD/DVD-ROM into your computer, and launch a boot menu to do a clean install.
Before doing this, you could swap out the hard drive and attempt to piggy back this drive using a USB external HD enclosure or another SATA/IDE channel on the computer. Ultimately, it is up to the vendor to provide you with recovery media and installation discs. I would recommend maintaining backups using a removable USB drive in the future.