After two weeks of digging and debugging, it turns out the problem was with our Device Class GUID.
After stripping our INF down to the bare minimum and comparing with another INF that DID properly preinstall on Windows 8.1, I realized that the only difference between the two was the class GUID. I did a quick search for ff646f80-8def-11d2-9449-00105a075f6b
and turned up over a thousand hits; not exactly what you want to see from a unique identifier.
I then looked back through 12 years of version control, and found that the person responsible for originally creating our device drivers didn't change the GUID in the wizard-generated INF from the Win2K DDK.
Creating a new unique class guid solved the problem, and our drivers preinstall properly on Windows 8.1.
I don't know if Microsoft is blocking preinstallation attempts with that GUID specifically, but the bottom line is: if an example says to change the GUID, CHANGE IT!
Here's the sample code for completeness. Don't do this:
;; ********* PLEASE READ ***********
;; The wizard cannot create exact INF files for all buses and device types.
;; You may have to make changes to this file in order to get your device to
;; install. In particular, hardware IDs and logical configurations require
;; intervention.
;;
;; The Win2K DDK documentation contains an excellent INF reference.
;--------- Version Section ---------------------------------------------------
[Version]
Signature="$Windows 95$"
Provider=%ProviderName%
; If device fits one of the standard classes, use the name and GUID here,
; otherwise create your own device class and GUID as this example shows.
Class=NewDeviceClass
ClassGUID={ff646f80-8def-11d2-9449-00105a075f6b}