The Everlys version of Paradise was certainly the first one I heard, on their "Pass The Chicken & Listen" album in 1972. It also has Guy Clark's "A Nickel For The Fiddler". Incidentally at the concert for a landmine free world in London recently (JP, Nanci Griffith, Emmylou, Steve Earle and Elvis Costello) JP stole the show, and their last encore was a communal version of Paradise.