First place to check for the Windows key is on the back or side of the PC case. This applies to pretty much all store bought PCs and laptops, as the manufacturer is required to attach the product key sticker to the PC as part of the OEM license agreement.
While most major PC manufacturers such as HP and Dell may have the key within the CD for automated installation, this is not the case with some less well known or generic brand PCs. All OEM CDs bought separately (e.g. as part of a home built PC) and retail Windows OS packages do not have the key located anywhere on the CD.
If you still have the Windows XP, Vista or 7 installation, even if not bootable, the freeware utility LicenseCrawler (link) will retrieve the Windows key. For a non-bootable installation, you'll need to run utility from a boot CD, such as Bart PE, Vista PE or the command prompt on a Windows Vista/7 recovery CD. Another useful utility for retrieving keys is Jellybean Keyfinder, but it does not work with Windows 7 (at least from a quick test on my PC) and the newer version which does has since become a pay product under the new name "Recover keys". :doh: