JST,
I have used electrolysis quite successfully in the past and the "black residue" you speak of was not a problem. It was there, but all it needed was a light going over with a wire brush and then a wash in water. The black was there but it came off very easily where as the rust was very hard to shift. Molasses no doubt would have done the job, but I quite like the results I have had with electrolysis up until now. I do use a very small battery charger though (4 amp max) and it cleans up quite large parts well, but it also cuts out if I put the anodes too close to the work. The fact that the small charger needs to have the anodes a distance away from the work to operate well may stop the black build up like you say you experienced. When I set the tank up I move the anodes in (usually one on each side) until the resistance is such that the charger is charging about three amps, and that seems to work fine, if I put the anodes too close to the work there is less resistance and the corresponding higher flow rate will trip out my small charger, if it was able to pass the higher current flow it may very well have made a "hard shell" like you have experienced.
Whether I still like the electrolysis method as much in the future may depend on how it handles my current project, because if I still can't move this brass sleeve in the next couple of days I will probably try it in molasses.
Thanks for posting JST, its always good to hear experiences other have had both positive and negative, I can file those away in the memory for future reference when something goes "pear shaped" (as it at times always will)
Graham