I've noticed on a few CPUs "Heatsink Req'd", then on seemingly identical models: "Heatsink & Fan Req'd" - whereas on others, no instruction at all.
I've barely ever seen fans on 486-class processors... is there really any point in 100Mhz + less?
It depends.
I had an AMD 486DX2-66, which required a heatsink+fan. It died after 2 years of use, presumably because the fan broke down. I replaced it with an Intel 486DX2-66 overdrive, which only had a heatsink glued on from the factory, no fan required.
Another Intel 486DX2-66 was in a Compaq Deskpro, which had a third-party heatsink put on (considerably larger than the one Intel put on the overdrive), and the case was designed so that the case fan generated airflow over that heatsink. The fan was probably overkill for the 486DX2-66 though, but the same case was also used for other machines. I have one with a Pentium Pro 200.
It could have to do with binning, perhaps they sorted them on fan-required and fan-less, depending on the needs for system builders (eg, I bet the overdrive CPUs were carefully selected, because they were sold as an upgrade for 486DX-machines, so they had to work inside systems that were not designed for anything more than a regular DX in terms of power draw and heat dissipation).
Another issue could be that later models used more mature manufacturing, so the chips ran less hot, and the fan may no longer have been required.
There have been some die-shrinks, and later 486 CPUs ran on 3.3v instead of 5v, so that also has an effect.
I guess you'd have to pay close attention to the details of the CPU, eg the build date and/or the serial number. They may explain why one DX2/DX4 is not the same as another DX2/DX4.