I would test the O2 sensor before discounting it as being the culprit although I'm still not sure how much a dead sensor will affect fuel consumption. If it hasn't been replaced in 100k or so a fresh one couldn't hurt.
Oxygen Sensor / Lambda Sensor Voltage Testing - Benzworld.org - Mercedes-Benz Discussion Forum
My TE uses fuel like yours. Not happy. I have a new sensor and injectors waiting to go in so it will be interesting to see what the difference will be. Substantial I hope.
Keep us posted.