All steel pickling operations I have seen use heated acid. The heat, of course, accelerates the action of the acid and would permit a lower concentration of acid to work as well as a higher concentration would work cold. In addition to Hydrochloric, I've seen Nitric and Sulfuric acid used, and Hydroflouric was used for pickling stainless steels.
I would follow the advice given earlier to babysit the process. You may find that a shorter acid pickle followed by a rinse and then wire brushing or wheeling would be preferable to waiting for the acid to eat everything perfectly clean. The parts may clean up nicely when they look like they are covered with black slime. You can always go back to the acid if it needs more time, but you can't replace good steel that gets eaten away.
I doubt that this had anything to do with your kilns' power loss at 750-800 degrees. The scale probably formed at higher temp when your aluminum foil wrap disintegrated.
