As per the circuit diagram ( which is a little sparse in true detail) the fan is powered from a relay whose coil is energised directly from the alternator output.
Your description implies that the relay is failing to operate. This is a plug in type automotive one that can be replaced. Given the wiring almost never fails and you fuse is ok this is a good bet to replace the relay. Check the voltages at the terminals and also try putting a 12 v feed to the motor to check it operates correctly.
Try that !!