I have this same problem. Where did you find the fan to replace the original?
But I also think this could be solved by a firmware update.
The fan always runs freely on FM3 startup, but when the temperature reaches 60 degrees, the fan runs at a speed what is lower than on startup and I see that sometimes the power to take the fan out of inertia is not enough.
If the fan was booted with the same FM3 boot power and then reduced after, I think it would work without problems, because if we blow into the fan hole it starts and continues to run normally, even at reduced speed.
I'm from Brazil and here the temperature is very hot at this time and most of the year, it only takes a few minutes for the FM3 to reach 60ºC and the fan beeps. I'm on my second FM3, the first one had already returned due to this problem but the new one has the same behavior in relation to the fan...