What completely unexpected or surprising song have you heard in a restaurant, in a store, listening to on-hold music, or somewhere else that plays “piped-in” music or Muzak?
I was in Breuggers Bagels last week. Breuggers tends to play some interesting music, but mostly stuff from the 90s (e.g. lots of Ben Folds and Indigo Girls types). So I was taken by surprise when they played Cuckoo Cocoon by Genesis.
Sitting in a Dunkin Donuts many years ago, waiting to start my day’s temping.
A sleek instrumental of Leonard Cohen’s “Famous Blue Raincoat” came over the sound system…
Also many years ago, before the days of satellite radio, etc, the Muzak playing in a depatment store in Clearwater, FL included an instrumental version of the Youngbloods’ “Darkness, Darkness”. Even more unusual: it wasn’t half-bad!
At a medium range family-type restaurant one night, “Cocaine”
Not too unusual being that it’s been used in commercials, but I still found Iggy Pop’s The Passenger an odd choice for a Krogers.
I was in Jewels (Chicago grocery) not too long ago and heard Head Like a Hole.
I must say it struck me as odd.
Eno and Cale’s Spinning Away
“The Cat Came Back” it was done by three strolling minstrels in a very upscale place…really surprised me.
A Muzak version of James “Laid” at Wendy’s in 1995.
Walmart played Walk by Pantera one time while I was in there.
I remember noting that the Muzak version of “Gangsters Paradise” was playing in the grocery store at which I worked. I normally wouldn’t have heard it but I was in the break room.
Monday Night Football once (I want to say late 80’s/early 90’s) played the opening riff off of The Church’s “Tantalized”-yes, it was after their brief fling with fame in 1987, but still…
Can’t remember exactly where I was, but I heard a Muzak version of Frank Zappa’s “Peaches En Regalia”
That could have been “Pastime Paradise” by Stevie Wonder, which Coolio sampled for his song.
At a Boston Market, Bob Holroyd’s fantastic cover of Peter Gabriel’s “Games Without Frontiers” (featuring my gal Hap singing the Kate Bush part).
I heard Hap played before a Vienna Teng concert, and again before a Charlotte Martin concert.
At a Regal theater recently before a movie, Rodriguez (from the soundtrack to Searching For Sugar Man).
I could swear ESPN used Manson’s “The Beautiful People” when they would go to commercial breaks during NASCAR races in the 90s.
Rio, by Duran Duran. Seriously.
But the ultimate has to be from a piece by Harry Partch called Barstow. Partch (1901-1974) was an avant-garde, classical composer. He spent part of his life as a railroad hobo during the Depression. He developed his own 43-note scale, and custom built instruments to play it. The text for Barstow came from eight pieces of graffiti he found on a highway railing in Barstow, California. Each is introduced with a short, repeated musical phrase and the words “number one”, etc.
So what public setting did this turn up in? Dr. Demento used to use it in his Funny Five countdown at the end of each show. So, Dementites and Dementoids, click here and see if anything sounds familiar.
This is, in a sense, the opposite of what the OP is asking. I heard the Dr. Demento clip first. The surprise was in discovering that something from a public setting was, in fact, unexpectedly quite obscure.
At a Chipotle restaurant, I once heard Blue Oyster Cult’s “Godzilla”.
Given Chipotle’s “happy food” stance, the lyric, “History shows again and again how nature points up the folly of man” is kind of appropriate. 
All on Muzak:
Weezer - Island in the Sun
John Mayer - Clarity
Pink Floyd - San Tropez
Now granted, they all work as background music, but none of them are exactly huge hits.
I was a ski resort in Canada and heard “I Won’t Be Your Yoko Ono” by Dar Williams on the lift line.