I've heard XTC's "Senses Working Overtime" twice at Sheetz (Mid-Atlantic gas station chain) in the past month. It's not completely obscure but there are probably 200+ other 40 year-old songs I'd expect to hear pumping my gas before that one.
Update: I heard The Corrs "Breathless" on my last grocery store trip too.
I posted about it on Facebook and my friend says they play it at the artisanal soap store she works at a lot too. Makes sense. I'd want to listen to the '00s soft rock if I was shopping for fancy soaps.