In addition to describing the 'dirt' and whether internal (clogged?) or external, you need to specify the HXer materials and type of construction: welded vs. brazed vs. gasketed. This way, one can determine the most effective cleaning solution.
For several types of all-SS (304, 316) welded HXers, I have used nitric acid to remove internal scale (hard water) and external deposits. Once clean and rinsed, used nitric again to passivate the SS.
Have also used bead blasting to do the primary cleaning of heavy external scale, with electrocleaning to finish up, again followed by passivation.
As tickle mentioned above, the HXer specifications should have allowed for proper cleaning without damage. For example, to allow nitric acid cleaning, welded construction is preferable to brazed.