One of the most interesting ways to reinvent a familiar song is to get someone of the other gender to sing it.
It says a lot for how music is conceptualised as being masculine and feminine when you experience the shock of hearing some baritone male voice singing "Hit me baby one more time", or Nina Gordon's delicate rendition of N.W.A.'s "Straight Out of Compton" (here's a link: to hear the song, click on the song title near the top of the page: be warned that the language is as strong as her voice is ethereal, but it's a perfect example of the cognitive dissonance I'm talking about).
This whole train of thought was sparked off by coming across Jonatha Brooke's excellent cover of "Eye in the Sky" (by the Alan Parson's Project), followed by the discovery of "An Acoustic Tribute to Dave Matthews", where (though I didn't realise it when I bought it) all the covers are by women. It's intriguing to hear some of my favourite songs from DMB recast in a more feminine light (though I must admit all 12 singers started to sound the same after a while).