Probably the codes were simple check-digit systems. Sometimes all zeroes or all ones works: http://opensourcerules.info/oem_key.html

For a while I had a Win95 product key memorised, for the frequent reinstalls that were a feature of pre-7 Windows.