great ! you found it !
I think it usually happens only to landlords with their kilotons
of keys hanging on the ignition lock.
little tenants like me have only 3 or 4 keys.
Just kidding!
Mercedes has since decades (20 years or so) the key in a separate
leather pouch. They probably know why.

You have to change the ignition lock.
There is something written in the FAQ about that.
I did not really understand it.
I tried to get a ignition lock out of a junkcar once,
but was not successful. When I came back with more tools the next day,
it was already gone. But I had all the other locks already
2 doors, glovebox , tailgate plus the keys.
Can't win always.

Another possibility is, when the 1st mech change the exhaust,
they disconnected the AMM (Air mass meter).
There are some reports about the contacts on the connector,
which are pulling back and loose contact.
You might wanna have a look and check that too, with engine off!