I've had trouble with the aux fanstat wiring connector, but you've already checked that out. I've also had problems with both the aux fan wiring in the fuse box. My thought is that the contacts overheat and slightly melt the supporting plastic, then you get a weak connection inside the fuse box. IIRC low speed is relay K1/fuse 3, high speed is relay K6/fuse 18. Wiggle the fuses, jump the relay socket to see if the wiring is OK.
I'd also double-check the thermostat bleed passage. The M42 doesn't have a bleeder hole in the thermostat, it's cast into the housing. Some have cut the paper gasket in order to open up the bleeder passage, others have drilled a small hole to eliminate that air pocket.
Is your water pump the newer model? The early plastic bladed unit impeller could fracture.
I'd also strongly recommend a pressure test. I had some similar problems on my E30, and it ended up being multiple pressure leaks. I found leaks in the heater core, and o-ring seals in the expansion tank. Oddly, the infamous cracking expansion tank was in excellent shape. Once I got all that done, the car held temperature perfectly. I only ran the engine-driven fan in the summer, removed it for the other three seasons. The car really didn't need a fan at all.
I've also found that mixing a little more water into the coolant really helped with bleeding. I run a 66:33 ratio of water to coolant with a splash of surfactant (RedLine WaterWetter or the like).