Another trick to try, is to cut up hot chicken right off the BBQ!
I kid you not. I did it with fresh hot BBQ sauce on my MUCK, and the patina was instant.
Then a while later, I cut up a bunch of chicken again and it went away (after scrubbing it with hot soap and water several times failed to get rid of it).
Take your knife and cut us some fresh poultry for dinner. It works for me!
I actually try different stuff to get the staining just for fun.
If you have a strop, even an unloaded strop, just give it a pass or two on the unloaded strop. If that fails, a pass or two on the loaded section of the strop will take care of it. It is much much less abrasive than scotch bright pads.
Some one else posted mother's polish, or flitz. Both work under the same principles.
After you spiff it up, what ever you use, make sure you give it a good scrub with hot soapy water. Some of the polishes are stuff you would not want to ingest even in trace amounts.
I did the strop polish for a few years on a GW and it still was not quite a mirror polish. It sure looked nice though. You are removing so little metal that it would take several life times to reduce the thickness of the knife doing this.