lza:
If I connect the gate (left cable) to 5VCC the fan starts after a short delay. If I disconnect the gate, the fan stops. Shouldn't it keep running?
No, because the 10k Pull-Down resistor quickly pulls the gate down to Gnd level [zero, or near zero, volts]. With the gate at a voltage below the threshold voltage, the MOSFET will be OFF [i.e. the channel will conduct *nearly* no current].
lza:
[If I connect the gate to 5V GND (common ground) the fan doesn't stop completely. It still clicks a bit and tries to spin (what ends up in a forward/backward loop because the voltage isn't high enough)
The statement "5V GND (common ground)" pretty much makes no sense, so not sure what you're asking. if the voltage between the Source and the Gate is zero, or something below the Gate Threshold voltage, the FAN should not receive any appreciable power, thus it should stop turning [after friction overcomes inertion, of course
].
Also, the IRF540 is a poor choice for PWM at such low Gate drive voltage, because the Gate Threshold is, potentially, rather high [4V max], and because the Arduino probably won't be able to supply enough current to charge/discharge the Gate capacitance rapidly enough [though, at the low frequency involved, this might not be an issue] A MOSFET gate driver [run at 12V] is a good idea. In fact, it's wise to just always use a gate driver for PWM.
And, as wolframore pointed out, you should include a flyback diode across the fan. A 1N4004, with the Cathode connected to the the 12V supply side of the fan, should suffice.
Have a look at my Blog at:
https://www.sinistercircuits.com//Blog/IsItLogicLevelOrWhat/index.php