Get some stainless-steel cleaner (Cameo, as suggested before, for example, although some people also recommend Bar Keeper's Friend) and, using a sponge, clean the flatware, rinse well, then run them thru the dishwasher. In my experience, there are a couple of things that cause that: one, it can be that the flatware is not made from the better stainless steel, those tend to react with mustard, mayo, lemons etc; two, even if you have excellent stainless steel, they *will* rust if you clean them with SOS and/or Brillo pads. As a matter of fact, you'd be better off washing all your pots and pans in the dishwasher and laying off the steel wool pads altogether -- if things don't come off the dishwasher clean enough, either run them thru another cycle, or clean them using Cameo. If you must wash them by hand with a cleaning pad, choose something that can't rust, like a stainless steel or brass wool pad, for example, or one of those 3M sponges that have a more aggressive side. I think the SOS pads are leaving small amounts of iron on your flatware that then rust in place.