radjabumbumbu,
Seems that your water is the culprit in the heat transfer operation. I imagine that the water outlet temperature is relative high, allowing for rapid deposits of calcium and other salts on the tubes, possible because of lack of treatment of the cooling water. The cooling water can be treated "on the run" if you are really desperate and the calcium could be dissolved with some relative harsh water treatment. However, it seems that you have operating problems, rather than exchanger design problems. Just remember, once you dissolved the salts deposits from your tubes, you have to remove them from the water somewhere downstream, otherwise you return the water to the hot tubes and the bad cycle starts again...Perhaps some blow-down equipment downstream of the exchanger...
Also, you did not provide sufficient details of you process and the equipment you are using. Trust us, nobody will try to steal your job and giving up details will only help you to solve the problems you have.
Now, if the fouling is on the gas side, you have not filtered the gas properly before attempting to cool it down, hence you need some sort of knock-out drum up-stream of the cooler to separate as much as possible of the suspended contaminants and send only the clean gas to the heat exchanger for cooling.
Regards, gr2vessels