Give molasses a try, Hal. It's a pretty strong oxidation remover. Leave it on it for several days. Won't cost much to try. If you try it I'd like to know how it worked, if at all.
304 stainless is very susceptible to chloride corrosion. Salt is a common chloride that will work on 304 pretty hard. 316 stainless is much more corrosion resistant. Bimetallic corrosion is a common cause of stainless discoloration and oxidation. Who knows what kind pots are made of. Some grades of stainless are not magnetic, some are. I may be mistaken, but I always assumed that the stainless grades that a magnet would stick to were the ones most likely to get rust specks.
