Варианта хороших собственно два:
1). Пескоструй, но выйдет думаю не бюджетно, но относительно быстро.
2). Долгий вариант - раскрутить батарею на секции и там уже пескоструй или же обычным корщетками/зачистным кругом на болгарке.
и сразу же покрасить/прогрунтовать каждую секцию, лучше спец. термостойкими красками и грунтами, не больше 3-4 слоёв, т.е 1 слой грунта - 2 слоя краски, или 2 слоя грунта -1 краски, тут зависит от укрывистости краски по грунту.
Минус - не быстро, разобрать, прочистить, покрасить просушить, собрать - с герметизации каждого стыка, но хватит надолго.
не уверен только что проще купить новые современные радиаторы, по крайне мере быстрее, но недешевле.
Greg_efremov,
всю батарею в ванну бросали или по секциями 
, концентрацию какую брали и время экспозиции сколько ?
способ хорош может быть, но явно не для дома/квартиры, требует участка и много воды для тщательной промывки после щелочи.
да макрофото поближе можно поверхности после чистки.