I'm a big fan, I have the Winged Cs in a couple of my Mesas, and they have been reliable and sound great. I like both the 6L6 and EL34s.
Two things to think about. Use only tubes with the correct mA rating that will bias properly. Mesas are fixed, non-adjustable bias, so you must the correct rating. I doubt your local mom and pop have any idea what that number should be. Otherwise the amp won't sound right. Beware.
And consider this: if your Electra-Dyne is under warranty, Mesa can and will void your warranty. If you have a tube problem that damages your amp, you could be SOL when the repair is not covered.
I'd play it safe if your amp is still under warranty. Replacing the originals with Mesa tubes will guarantee that your amp will still sound good, and you'll keep your warranty intact. And, if they fail, Mesa has the best tube warranty around.
Bill