This kind of thing is easy for MS to solve
All Microsoft need to do is provide downloads of the correct DVD. You just go on the website, enter your product key from the sticker on your machine and download the ISO. Anyone who manages volume licensing will know that most of this is already in place for VLK customers.
If I need a copy of Windows or any other Microsoft product at work I just go to the website and download.
The thing is you can't win, I have a Toshiba laptop, it came with Vista preinstalled and recovery CDs to reinstall XP or Vista. Do I know where those CDs are? Hell no.
My Acer Revo had a recovery partition but I wanted the space back it was taking up and the Revo doesn't have a DVD burner to produce the discs so that recovery media is gone.
If both these copies of windows were available in the cloud we'd be fine. Microsoft could limit the number of downloads per key to stop abuse. If you need to download the CD more than 5 times you're probably doing something wrong.
If Microsoft don't want to do this themselves maybe they should provide it as a service to the OEMs. Then the OEM can advertise that as part of their product. I for one would make sure I only bought computers from an OEM that offered the service.