Well, I can tell you that the first fans were not used until the 386DX's came out. Some people were just buying a 386SX, overclockign it to DX speeds, slapping a fan on it, and selling it as a 386DX. Back in those days, the difference was several hundred dollars. I want to say that heatsinks were always used in microprocessors, but I could be wrong.
