Radiohead song covered by jazz pianist Brad Mehldau on two of his albums (Art of the Trio 3 and 4), in live concerts and recorded on KCRW's Morning Becomes Eclectic radio show. He stays very true to the original, aside from the solo section over the song's final chord progression. The poignant beauty of this song really comes through as a piano instrumental. As Mehldau himself put it:
When I first heard Radiohead play that, I thought, god this harmony is beautiful and evocative of something that could be right out of St. Mathew's Passion or Bach, or an aria for some opera. It has that tragic quality to it that immediately appealed to me.
Mehldau also covers
Paranoid Android in concert and on the
radio promo
Deregulating Jazz. I'm sure you can find
mp3s of both of these online.