I hear the strangest covers thanks to my friend Jessica. She loves music she grew up with in the 80s, but hates . . . well, 80s music. I heard a sort of punk version of the "I will walk 500 miles" song. She's got a handful of different "Phantom of the Opera" versions, including one where the singer actually sounds like a real stalker.
She's got tons of "Route 66" covers, which coincide with her storyhour here: High Fantasy - Route 66
And then, my personal favorite, is it cover of 'Hit me baby one more time' that's sung by a guy with, again, a sort of stalker-esque voice. It makes the song interesting, rather than what it is.
But I can't be involved in this post without mentioning the greatest cover ever (but not appropriate for your list). Queensryche's "Scarboro Fair" is amazing.