Some fans have a built in speed sensor (tach) that feeds back a signal to the Motherboard. This lets the Motherboard know that the fan is actually rotating and at what speed.
This is typically done by having a tiny magnet attached at the hub of the fan blade. As the fan rotates, the magnet comes near a magnetic sensor (hall effect) on the motor housing or mount. This is also done with optical components rather than magnetic.
As a fan is used, a typical wear point is the bushing (or bearing) where the motor shaft extends out from the motor to attach to the fan blade hub. This wear can let the fan blade move closer to, or farther from the motor housing than it was designed to do. As a result the speed sensor can fail. Starting and restarting the fan (computer) could eventually let the fan blade move into the proper position and it will begin working. So, the fan could appear to be working fine (mechanically) but actually have a problem.
Fans are pretty cheap compared to other repair components so, depending on the age of the computer, I would just try a new fan and see if it was the problem. If you want to be sure, I would take the computer to a small PC shop and buy the fan and install it on the spot. You should know pretty quickly if it was the problem.
I don't know if you have working relationship with PC shop. The one I use would be happy to take a test fan from their workbench to try it out before I needed to buy one.
Your particular fan may or may not have a speed sensor but I suspect that it does. Systems that do not monitor fan speed will usually monitor CPU temperature instead. As the CPU temperature increases, the system drives the fan faster and faster. If the fan isn't spinning fast enough (or not at all) to properly cool the CPU, the CPU temperature will eventually get too hot and the system will slow the CPU way down, or display an error message and halt the computer. But, it is not likely that the CPU could heat up quickly enough for the failure to show up at boot time.