Accidentally left grill grates outside during the winter and rust built up.
Tried to search online and ask at Lowe's, but didn't find a good solution.
What worked for you?
Put them in the grill and get them HOT! Then use a wire brush and scrub the scale and rust off. After that I usually coat them with olive oil but any cooking oil will work.
Soak them overnight in vinegar. It works like magic to remove rust. Afterwards rub them with oil or they will get rusty again.
Put the grill grate inside the container making sure that it is not lying flat on the bottom but have room for fluid to move under it, place some stands under it if needed.
Place non-conducting thin spacers on top of the grill grate and put the iron plate on top of that (e.g. parallel but not touching). Connect correct electrical wires to each of the grate and the plate.
Put on the gloves (safety glasses are also a very good idea), mix sodium hydroxide and water in a bucket (warm water dissolves more quickly), and pour the liquid into the container, repeat if needed until fully covered.
Turn on the power source, it should start to bubble a little and you see rust being generated. Let it stay until done. You might need to clean the iron plate from time to time (although if you do not the process only goes slower).
When done, take out the grill grate, dry it and brush it with a wire brush and enjoy your almost as good as new grill grate.
The above is just the general instructions, look up a couple of the hundreds of tutorials on rust removal electrolysis available on the internet for details.
From the pictures you see that I got hold of a quite large iron plate. It is not strictly needed to have one that fully covers the grill grate, but it will ensure even coverage (with uneven coverage just move the anode around over time or just let it run longer). Concrete reinforcing rods are an alternative. Using graphite instead of iron as the anode is a better solution as it avoids making the liquid so messy, but I have not tried it.
The waste from this should be safe and non toxic, but check with your local authorities for disposal. And again no stainless steel! Also avoid copper wires inside the solution.
The most reasonable low-labor suggestion for a homeowner is an angle grinder with a wire cup. It's a moderately priced tool that will likely be useful for something else down the road.
A no labor solution is electrolysis, which will pull the rust off. However it involves an electrical source, water, and home-made wiring so you should be somewhat comfortable with basic concepts of electricity before employing google-fu.
Just as another option, you can use lemon juice and salt as a scouring scrub for the rust (this is a technique borrowed from cast-iron skillet maintenance) that is (obviously) food-safe. Squeeze lemon juice onto the grates, salt them with coarse salt, and then use a half lemon like a scrub brush. It's kind of a combination of the vinegar (acid) + wire brush (abrasive), with inherently food-safe stuff.
Use Evaporust. Non toxic and amazing.
Wad up a sheet of aluminum foil and scrub the grate.