> I've heard that welding stainless steel gets it too hot and removes something (the carbon?) essentially de-stainlessing it (?).

I don't know if it's possible, but even if it is, it's not the carbon that makes the steel stainless. It's the additional chromium, nickel, or molybdenum.

Maybe when the steel melts during the welding process, those other metals get separated from the iron.