@PiR:
I dont mean the voltage drops caused by the resistance in the cables and the motherboard power supply lines. When you hear the fan loose rpm temporarily when it is connected directly to the power supply it cant be the cables. The resistance in cables could only cause a constant lowering of the voltage and alas fan rpm.. and a cable with great enough resistance for that when powering a little 5V fan would probably have to be as thin as 0.01mm. What I am trying to say is that it definately sounds like your power supply is acting wierd and I would urge you to try another one... if it doesnt sound like a good idea to you, atleast consider doing it just for the sake of it.
/Patrik