[The following is from before the latest patch (KSP 1.7.1, BG 1.0). I understand that the new patch makes them easier to find, but I haven't tested that myself.]
I found one sandstone on Minmus, but it was *bleep*ing hard. I had Bob fly at a few hundred meters over the surface, and the looked for a pixel that twinkles just that bit differently... The Olivine formations are somewhat easier to find, but I don't have the scanner arms unlocked yet.
So they do exist.