When you say that the fan does not always start, do you mean at all ever during the car being on or do you mean right away. If you mean right away, the fan will not turn on right away all the time. It's not supposed to. If it really does have intermittent response, it could be due to bad wiring or a bad fuse. It looks like you've hit all the electical other than that to control how the fan behaves.
If your fan is working fine, and it may be....it could be that your water pump is bad or leaking. How many miles are on the car and when was the timing belt/water pump last services/checked?