Stopping and starting? How erratically? If it's literally completely stopping, and then coming on again - I'm not sure that's normal?
At least, in my personal experience, fans which automatically adjust given the core temperatures will gradually increase/decrease their RPM as the temperatures changes.
However, perhaps there are some which are meant behave in the way you have mentioned. I'm sure someone can verify this.
Since you mention random power offs, I'd certainly be concerned about your PSU. It may be causing the CPU fan problem (if indeed it is problem). I don't know much about rails etc, so I can't comment, however from what you've described you may have a PSU issue.
What model is the PSU?