I've actually had the chance to listen to a variety of Sennheiser headphones at my local media store. The unfortunate part is that many of the display models come with the obvious problems of being that. For example, I've tried the HD 600 there and they sound and look absolutely horrible, but I've got no idea how much of that is due to it not being new. I wish I new a dedicated place for headphones around here, but all I can think of is a particular HiFi store, the kind of place where anything below 400 bucks will get you The Stare. I will keep browsing around this place though!
The 518, 558, and 598 all sound increasingly better from what little I could tell in the store. By just how much though, I can't tell within the few minutes of testing I can do in that local environment, plus the fact that I can only use the propietary sample music tests provided there or my phone, which obviously doesn't come close to anywhere I'm using these most of the time (my computer).
HD 600 should not sound horrible due to being used. It's high impedance, so if you had it directly connected to your phone, its amp is likely too weak to power it, causing it to sound crappy. If it was connected to the store's amp, might also be too weak, or might be something wrong with that display model. I'd ask a store rep if they're supposed to sound that crappy or is something wrong with them. Small chance they may swap them out with a new pair. Unlikely though.
Take as much time as you need in the store listening. They can stare all they want. I doubt anyone will tell you that you're taking too long. They ought to know that guys with headphones are like women with shoes! lol
If you have a premium phone, it should sound pretty good with most low impedance cans. At least you're using the same device when comparing all cans, and that's what really matters.
Of course, if you need more time alone with them, and hooked up to home gear, try to buy from a store, local or online, with a good return policy.