I have used all of the methods mentioned and generally a combination of al thr above is needed. The ultrasonic cleaner is by far the best bang for the buck and the least labor intensive. If I had a pile of bolts off a grimy 40 year old block I'd soak them in your Solvent of choice (simple green and purple power are my favorites) to get the heavy stuff off first so you dont trash the solvent in the ultrasonic cleaner.
Follow up with 15 -20 minutes in the ultrasonic. I have a good general ultrasonic solvent to be the best in there. I tried dedicated ultrasonic rust removers but they did not work significantly better. If there is any rust left then you hit it with the wire wheel.
Good luck