To answer your questions:
1. I just brought the car in for an oil change and front pads and rotors a couple of weeks ago. Before that, was probably in November for a 75k mile tuneup.
2. The fuel I use varies but I mostly use Valero here in the SF Bay Area.
3. I can't say when the O2 sensor was checked. I just bought the car almost 2 years ago and have not had a "major" tuneup on it yet. The next big one will be 90k.
I used to do maintenance on my own cars but in my old age (35), I just send the car out to an independent MB garage that comes highly recommended by a friend. I would be willing to try changing the O2 sensor if it's pretty easy to do.
1995 E320 Wagon
1996 Volvo 850GLT