Is there a relay in the fan compartment? Seems like a pretty trivial job for a 3P2T relay. "Fan Out" on NC / "fan in" NO with the heat switch powering the coil; with the neutral on the third pole as double-throw.

Joe: in your diagram, the fan switch does nothing, and the fan comes on with the light?