Ah, good questions. Although we are missing a lot of rock, paleontologists have spent a lot of time looking through the non-missing parts. So far, they have found a lot of really interesting things, such as the macroscopic soft-bodied fossils of the Ediacaran biota [1], but even so there's really very little in the way of shelly fossils until the Cambrian, and their appearance really does seem to be quite sudden as far as we can tell!