Wow...
SOMETHING will likely work... just a matter of what. I know this may sound stupid, too, but try a Magic Eraser (extra strength). Whatever they put in that thing is STRONG - it's been known to remove tar from vinyl siding and other such feats.
Just crazy. I've had a few bad experiences with detailing shops... and I HATE when they try to do things like freshen an interior. A BMW interior that smells like fresh leather needs no freshening!