Well theres no evidence that xenon does deplete b12 , and i believe that not all nmda antagonists deplete b12 , so it must be something specific to nitrous oxides pharmacology.
Vitamin b12 uses a cobalt molecule to perform methylation reactions. These require the cobalt to oxidize and reduce (something metals are great at). Nitrous oxide(NOO)actually doesn't do anything to b12, but it spontaneously breaks down to nitric oxide (NO·), which forms a pretty much (for the context of a biological system) irreversible bond with the cobalt, locking it's oxidation state.
A similar process is carbon monoxide (CO) binding to iron in hemeglobin.