If they prove to be more a stubborn, chemical surface reaction....an abrasive cleaner to a metal polish to auto cutting compound would be the route....plunging them in your brothers stomach for a quick acid bath is probably a little extreme /img/vbsmilies/smilies/wink.gif.
If it's hard-water deposits you may have to use a mild abrasive. Try Bar Keeper's Friend---the powder, not the liquid, cuz the liquid is the next best thing to useless.
Combine a little BKF with water to make a paste. Then use a soft, damp cloth as the applicator. Wet the knife and gently rub with the paste. That should remove any of the spots and polish the knife in the process. Wash as usual and dry immediately.