I happened upon a cover of Leonard Cohen’s Hallelujah that made my jaw hit the ground. It is by Justin Timberlake who I know is a quality musician, but still, fuck me.
Find any yourself?
I’m not sure exactly what you’re asking for. Is it that you wouldn’t have expected that person to cover that song, or that you wouldn’t have expected that person’s version to be good but it was, or something else?
I despise that wretched boring dirge. I find that version is equally a dire as all others I’ve heard.
Curiously, two of my favourites are by Faith no more. “Easy” and “I started a joke” which was all the better for being unexpected and making Terry Christian look a bit of a dick.
Not heard the Justin Timberlake version myself, but it can’t be any worse than the truly appalling version that Alexandra Burke (UK X-factor winner) crapped out a couple of years ago.
I’ve got at least three versions of that song, all of which were brilliant, but I just can’t listen to any of them since hearing that version.
Sheryl Crow had no business what-so-ever covering Sweet Child of Mine.
I was a huge Motley Crue fan in high school. But their version of Anarchy in the UK (USA, whatever) made my teeth hurt.
Mary Margaret O’Hara wrote a hauntingly beautiful song called Dark, Dear Heart.
Thensome other chick re-recorded it, with none of the charm and mystery of the original (because, come on. If you aren’t Mary Margaret O’Hara, you can’t do justice to her songs). Burn! Burn! Burn!
Britney Spears doing a cover version of I Can’t Get No Satisfaction probably deserves mention.
but their cover of White Punks on Dope was rockin’!
That is stunning. Has she ever recorded this in the studio?
I’m not sure if the OP wants covers that amazed us with their goodness or amazed us with their badness, so I’ll post one of each.
The good: Pantera - Planet Caravan. This isn’t the best cover I’ve ever heard, but it is one of the most surprising. At the time, I didn’t know Pantera had it in them to sound so…trippy. (The video leaves a lot to be desired, though.)
The bad: Scott Weiland - Let Down. While I am a rather large Radiohead fan, I have no problem with them being covered and quite enjoy hearing different bands do so. This, however, is just bad karaoke.
In general, my response to queries of this sort is “Don’t Think Twice, It’s All Right” by the Wonder Who (actually the Four Seasons). However, I think that was intended to be funny.
A lot of punk/New Wave bands did witty covers… like Devo’s “Satisfaction”.
Hey, and how about the Beatles’ shambolic jam on “House of the Rising Sun” (from the Get Back sessions)?
I got dial-up, so I’m immune. As far as bad Pink covers, Dar Williams 
kinda puts a dent in Confortably Numb.
Polyphonic Spree’s cover of Nirvana is pretty interesting.
Wow. The rich and amused insulate themselves from the pain of the common poor. 
On the opposite end of the spectrum is Richard Thompson - Oops I Did It Again - YouTube
But it can’t touch this version.
My wife and I have seen Holly and Mary Margaret perform together on the same stage, and know that they’re friends. One other thing - Mary Margaret has released one critically acclaimed, but poor-selling complete album in her entire career. The songwriting royalties of one song on a Holly Cole album probably earned her more than Miss America.
Except that’s awesome! 
Faith Hill singing Piece of My Heart is less so.
Yeah, I wasn’t sure if we were supposed to be going with awesome or hideous in this thread, so I went with awesome. 
Speaking of Nina Hagen (well, gaffa linked), one of my favorite bizarre covers is Nina Hagen’s “Zarah” which is even cooler when you hear the original by Zarah Leander. OOOND OOOND OOOND OOOND!
Nina’s a nutcase (so was Zarah) but I can’t help but smile at her covers. “Ave Maria” is actually really good and fairly straightforward (well, for Nina), and who better to sing “My Way” than Lady Gaga’s grandma?
Thank you for listening! No, she’s never recorded “Space Oddity.” She only performed it live a handful of times. The only Bowie cover she’s ever officially recorded was “Ashes To Ashes”, for a special-release EP, and a compilation album. I’m pretty besotted by her own music (she has 11 albums of original music) but I think most of her covers are pretty killer because her voice just kills me. If you’re interested, here are a few more that I, biased though I may be, think are smack in the face covers. I’ll put them in spoilers tags for those who don’t want to see the list.
[spoiler]
“Lily of the Valley” live (Queen cover. There are other versions)
“Soon” live (Yes cover)
“The Yes Medley” (album version, I don’t have the live version she performed at YesFest)
“Mercy Street” (live version) (Peter Gabriel cover, here’s an album version)
“Here Comes The Flood” (Peter Gabriel cover)
“Come Undone” live (Duran Duran cover)
“Don’t Dream It’s Over” live (Crowded House cover)
“And Dream of Sheep” live (Kate Bush cover, alternate live version)
“Into The West” live (Annie Lennox cover)
“Immortality” (Bee Gees cover. I know I know, but it’s so beautiful!)
Not a cover as such, but she incorporates Kate Bush, Yes and Bowie into this song:
“Feed The Fire” (Acoustic Tribute version)
Last, this is a Bob Holroyd cover of Peter Gabriel’s “Games Without Frontiers” where Hap sings the Kate Bush part. It’s one of my favorite covers.
Lest anyone think I would post video of her singing the phone book, you’re being spared some not so hot covers. Love her dearly, but her “Station To Station” just did not work. I’m not all that crazy about the Ashes To Ashes cover I posted above, but it was pertinent to the discussion and a rare recorded cover.[/spoiler]
It was my pleasure. I love listening to covers, especially Bowie covers. Now that I’ve checked out all of the links you posted, I’m a little embarrassed that I’ve never heard Happy Rhodes before now. What a sensational voice she has. I see there’s a YouTube channel of her albums, so I’ll be getting better acquainted with Ms. Rhodes very soon.