I think I remember this song as "Him" by Rupert Holmes from his 1979 album "Partners in Crime". But this track has appeared also on many other albums as well. I am also very familiar with the phenomenon of hearing music in a public place and wanting to know what it is!