After setting up Windows 95 in a virtual machine, I noticed that it could verify the product key without internet (no serial ports or network adapters).
From modifying a genuine key at the CoA (Certificate of Authenticity) screen, I noticed that it was very sensitive about the first four digits of the first box of the OEM key (an OEM key for Windows 95 was 5 digits-OEM-7 digits-5 digits), and the entire 7 digits of the second box, but was very lax about the third: it even accepted 00000 and 99999.
How did it know when a product key was invalid or not? If I typed in some random numbers, I got a pop-up that read
the Certificate of Authenticity you enter is not valid, so there was some verification.