The restore CDs that the OEM included with the computer still had all the crap baked into it. You needed a retail copy of Windows and hopefully someone hadn't ripped the OEM key sticker off the computer.
The OEM key would be usually encoded into the BIOS on newer releases of Windows, and could be read from a working Windows install using a freeware utility. In practice, it was unlikely you'd have to reinstall on a freshly wiped PC that you don't have an OEM key for.
