I think I found a solution... I will try to explain it, but it may not be clear.
The temperature sensor is a non-linear device - the resistance of the sensor varies exponentially with temperature, so a lookup table is used to linearise the input for the ECU. This means that at the steepest part of the resistance/temperature curve (the most useful bit in my case), a large temperature change might only cause a single bit change in the A to D converter.
So, given that there might be a bit of noise in the readings, a single bit change in the A to D may in fact be a larger temperature than the hysteresis parameter for the fans.
So I increased the hysteresis until the problem went away. It is now 4 degrees instead of 3 and no sign of the bad behaviour.