Okay, I will jump through the hoop... this time.
When did MS start using product keys? Win 3.11 certainly didn't have them, based on lots of installations of that that I've done recently.
Windows 95 had it, but Office may have had it earlier. Xenix uses serial numbers, but I don't know whether that came with the SCO involvement or not. There were probably other products as well. Windows for Workgroups 3.11 does ask for a serial number, but doesn't require or validate it; Windows 3.1 does not ask.
What did MS use before product keys?
Microsoft Works (and likely many others) "brand" their installation disk during first installation. Reinstallation does not allow you to use a different name or company. Microsoft also used various forms of copy protection (such as in Microsoft Adventure).
Why did MS start using product keys?
To combat software piracy, forcing people to buy more copies instead of copying.
When product keys started being a thing, were they linked to the BIOS of the motherboard, or did you just have to have any valid product key?
Windows 95 is fine with any valid product key. It validates using a built-in algorithm. There is no external verification, network/internet access wasn't common.
Were they linked at all to the hard drive? For example, if I acquire a used unit with a valid sticker and the HDD is corrupt, can I install a new HDD and install Windows on to it using that sticker?
Product keys in Windows 95 are not tied to the hardware by technical means; reusing is possible.
Are product keys transferable between versions of Windows (98, XP Home, XP Pro, Vista Home, 7, 8, 10, etc.)? For example, can I have a unit that has a Vista sticker and Vista installed, but use a disc and install XP or 7 over Vista?
Legally, depends on your license. Some higher-grade licenses allow you to downgrade. That is a Microsoft policy and therefore liable to change.
Product keys are not licenses.
Can I scavenge product key stickers from units that are being trashed so I can hopefully re-use the product key on another unit whose sticker was scratched off before I acquired it?
Legally, no.
Product keys are not licenses.
How do the product keys work? Is there an algorithm in Windows that can independently generate (and thus validate) any given product key? Is there some gigantic master list that they started with at MS HQ and sprinkled the product keys out to all the units they produced, only one key per unit?
Different technologies have been used in different eras. Different distribution mechanisms have been used for different products. Different variations have been used for different customers. Not a good question.
Does MS seriously still honor registration by telephone? In which case, what information do they make to tell them, and what information do they tell you? Is there some particular number of registration calls before you get red flagged by their records and they won't play with you anymore?
No idea. Haven't tried. Microsoft is also unlikely to tell you. Not a good question.
What is a volume license?
You might want to look at [
Wikipedia]. Again,
product keys are not licenses.
It seems that the XP activation key algorithm has leaked recently. Anything newer than that is probably not even close to "vintage" yet.