Yea, when I was last looking around at cars (which lead to buying the C230) I seriously considered a hail damaged outback, the price was 4k below market, but after tallying up the costs just for the external panels and paint, and doing my own work, it would have barely broke even, and I have the salvage title on it. I suppose I could have pulled and bondoed a lot of it, but that adds a lot of time and the repairs are never quite as good as new panels.
On the topic of the E500 - I don't really pay attention to the E-series forums, so I don't see what those guys complain about. As was recommended before browse through the benzworld, and mbworld forums for the E series, see what shows up (especially stickies.) The other thing is Consumer Reports, I always check their used ratings - I did a quick check on the E series V8, and there's a surprising set of poor marks for electrical systems, suspension, and body hardware for the 2004 year. How much that really means I couldn't say.
Overall my suggestion would be to go see the ones you're interested in, if you have a mechanic friend who will go with you, even better. Nothing like seeing, hearing, and feeling a car first hand for knowing what condition it's in.