Thanks @DirtyGary, that really helped me work this out.
I've been down this rabbit hole and found this https://h10032.www1.hp.com/ctg/Manual/bpb12296.pdf (which is mirrored here on the Retroweb.)
Basically the entire series looks to have used the same motherboard, but with different options on CPU, RAM, Video RAM and cache (for example the 4505 shipped with no cache, 16Mb of RAM, 1Mb VRAM and a P166, the 4528 on the other hand shipped with 256kb of Cache, 32Mb of RAM, 1Mb VRAM and a P233). The board appears to be this one on the Retroweb.
There are two recovery sets available on Archive.org:
Those BN numbers are important as this is what the restore CDs us to identify the system being restored, and is referred to as the "Configuration Code" for the various models. The serial numbers for these units are in the format of:
1234BNxxA567
where BNxx is the identifier (see the PDF linked above for a reference table of the various configuration codes).
So to get either of these restore options to work, you simply enter the machine's serial number, but change the numbers after the BN to an appropriate number that works with the recovery media (2A, 52 or 28).
And lastly for anyone who wants to know how I worked out what media works with what model identifiers, that is pretty easy. It's in the \MAP\BOMID.TXT file in the ISO.
I am mostly posting this here for posterity, and because this may also apply to other such Compaq series of machines of the time.