1) sense if the fan is using current or not (this can be done with non invasive sensors on the line cable of the fan, but those are oftene analogue so you need also a ADC). Fail if the fan is blown up and simply heats up the motor instead of turning

2) put a "wind speed" sensor in front of the fan. This is far more expensive, but has the pro that can be used also if you want to control also fan speed.
3) put a "bend sensor" in front of the fan
4) put a hall sensor and a couple of magnets near and on the fan (i say a couple not to unbalance the fan rotating). This is cheap and let you know all the above. The cons is that mecanically is harder to obtain.. and you have to check the "resolution" of hall sensor (if fan is turning fast maybe you loose some contacts)
wow a lot of options
