Hello everyone! First time poster; have been lurking for a few months now ever since I bought my 1995 E320 wagon in Feb 03. I had to post on this one, as I experienced exactly the same thing, and fixed it!
My car had 53K miles when I got it; all was perfect except for the sulfur smell and miserable mileage (worst tankful was 13 mpg 70/30 in-town/highway, best was 20 mpg, not too bad, but ALL highway 300 miles). The car ran really well; nice idle, good acceleration, etc. Just stunk! Took the car to the dealership for full inspection right after purchase, the mechanic noticed the smell as well and said he could not get reliable diagnostic read from computer because "too many things were reading incorrectly". He said I needed the HFM wiring harness, $805 for my car their price, plus 3.5 hours labor @$90/hr. Cha-ching!
Did some searching on this site, and it turns out there are two different part numbers for our car for the harness, depending on date of manufacture. The part number can be found on the harness behind the battery (you may or may not need to remove the battery to see the number, just check along the side of the battery for a thick bundle of wires with a large white tag on it. The tag has bot the part number and date of manufacture (convenient!) stamped on it. Be careful not to manipulate the wires too much, for if they are anything like mine were, they are very brittle and too much movement can cause a shorting out situation. I recall that my part number ended with 29 33, sorry I'm not more help here but I'm on vacation and have nothing in front of me to see my number. Do a search and you'll find lots of info.
This particular number harness is one of the more expensive ones if not the most expensive. I got mine from Fastlane for $675. Put it in myself over 3h. I change fluids on my cars, not much more, and this job was relatively easy. You do have to be a contortionist to get a few of the connections, but it's not impossible. If you want more info on how to do this, either do a search or just let me know. All the info is already on this site in the archives.
Long story a bit shorter: My worst mileage has been 18 mpg mostly in-town driving, my best was last weekend 90% highway and 25 mpg. Sulfur smell eliminated completely! Runs the same as before! Pulled apart some of the old harness and the insulation on the wires was cracked every 5-10mm, but only on the parts of the harness that saw the most heat from the engine.
Maybe yours is bad? Sorry this was so long!

__________________
Brian
1995 E320 wagon