I think what we're trying to avoid here in our writing is not awesome characters who are smart and beautiful and have cool abilities and are destined to become the One True King, but rather stereotypes. Personally, I like reading about characters I might aspire to be. Just give them depth and an interesting obstacle to overcome, and that's a pretty good start.
I've thought of what might be classified as a good Mary Sue:
Captain Carrot Ironfoundersson, from Terry Pratchett's Discworld. He's strong, liked by everyone, a natural leader, possibly even subtly clever, and the unacknowledged-but-everyone-knows-it heir to the throne. The author purposefully started him out as a stereotype, but he's evolved into my favourite character in the series. (Except maybe Sam Vimes.)