The chorus of “Lonely no More” by Rob Thomas (fast forward to 0:43) sounds like the chorus of “Me and my Broken Heart” by Rixton.
And “'Till the End of the Day.”
He messed it up by marrying her?
Beyonce’s “Halo” and Kelly Clarkson’s “Already Gone” use the same background track. The producer (the guy from One Republic I believe) sold them both the same track.
I’m wondering how this thread went from “the same song that sounds different” to “different songs that sound the same”. Because we’ve had dozens of the latter but not any of the former that I remember.
Oh. In that case Brain Damage by the Austin Lounge Lizards.
Paging Calhoun Tubbs! 
I first heard this tune performed by Ritchie Blackmore’s Rainbow.
I didn’t know at the time it was a cover of a very old, very slow, kinda lame Yardbirds tune.
My favorite folk tune recorded in the early 60’s with a charming nonsense chorus and tragic antiwar lyrics was “Gone the Rainbow.”
www.youtube.com/watch?v=aAKzg5fqSqg
Flash forward nearly 50 years, and there on TV are the Celtic Women singing the
same song but that nonsense lyric
“Shule, shule, shule-a-roo
Shule-a-rak-shak, shule-a-ba-ba-coo
When I saw my Sally Babby Beal
Come bibble in the boo shy Lorey” was actually
“Siuil, siuil, siul a run, / Siuil go sochair agus siuil go ciuin /,etc…” Gaelic that was ancient before I first heard it. Gave me chills.
In my case it’s because I didn’t read carefully enough. Oops, sorry.
I made the same mistake.
Charlie Parker and other jazz pioneers took the chord progressions of familiar old songs and created new bebop songs over them. (One such example is “Donna Lee”, which was based on “Back Home in Indiana”.)
There were instances where the process wasn’t completed, and the result was a version of the old song that was still listed under the original title, but pretty much unrecognizable (which is what the OP was asking for.) One example: “Embraceable You”.
It took me a while to realize that Limp Bizkit’s “Take a Look Around,” from the Mission Impossible 2 soundtrack, uses the familiar melody from the old TV show Mission Impossible.
I’d always liked Steeleye Span’s “The Weaver and the Factory Maid,” and I’d always liked the Cheiftains’ second album. One of the Chieftains songs vaguely echoed some song or other, and finally I realized it was the Steeleye Span song. Turns out they’re the same folk song (the title of the Chieftains version is just different enough that it wasn’t obvious to me.)
One evening, in a pause in conversation, in the background we heard Tori Amos singing “… With the lights out, it’s less dangerous, here we are now, entertain us …” It was quite startling, because it was well into the song before we realized what we were hearing.
This is a slight deviation from the OP criteria, but: I always kind of wonder why so few people seem to talk about the fact that the theme Fred Armisen wrote for *Late Night with Seth Meyers *is, essentially, Deutschland Uber Alles.
(The only online mention I’ve been able to find is a Google Groups discussion at Redirecting to Google Groups
excerpt:
An early rock song (1960), and one of the tracks from the first Miriam Makeba album, released a few months earlier:
https://www.youtube.com/watch?v=d99wc8LGDpwHow about Neil Sedaka’s two versions of “Breaking Up is Hard to Do”?
That reminds me of Eric Clapton’s/Derek and the Dominos’ two versions of “Layla.” It took me years to realize they were the same song.
I’d listened to Bruce Springsteen’s Live in Dublin dozens of times. Likewise Nebraska the album. I discovered, to my vague amusement, that there was a song called Atlantic City on both. Months later I realized, to my immense embarrassment, that it was the same song.