Having windows and linux on the same machine is definitely doable. Generally, the easiest way is to start with installing windows, then install linux. In your case, you're attempting to do the opposite - not a big deal, just a few extra steps needed.
Regarding your recovery disc (?) not working, I do no think the issue is related to VL, specifically. Also, if you did not make any changes in your BIOS then the issue should not be related that either. Some systems (laptops included) actually have a recovery partition on the hard drive. This recovery partition is generally accessed during the boot; you'll be prompted to press a specific key to enter "Compaq Diagnostics/Utilities" (or some such thing). The recovery partition can generally put the hard drive back to the manufacturers original state (i.e. EVERYTHING ON THE HARD DRIVE, ALL DATA, WILL BE LOST). My recommendation would be to get the laptop back to manufacturers state (backup any of your linux data because it will be lost), and then use a tool like Gparted live cd to shrink your windows partition, and then use the VL installer to install to the space you created.
Now, if you don't have a recovery partition then somehow you need to "convince" your laptop that the recover disc you have belongs to it
. The convincing part is what's in question.
Is the recovery disc you created a CD? DVD? Floppy?
I don't know if any of this will be helpful to you, but hopefully something sparks a thought.