How are organic walled microfossils preserved in the fossil record?
Organic-walled microfossils (wether they be dinoflagellates, pollens, spores or "acritarchs")  all have in common to contain an organic compound known as sporopollenin (for the spores and pollens) or dinosporin (for dinoflagellates and, I believe, acritarchs as well). Both compounds have chemical and structural similarities but have appeared independently. 

Those compound are incredibly resistant. To give you an idea, to collect siliceous microfossils we first dissolve the sediments with HCl (hydrochloric acid) to get rid of carbonate microfossils. Palynologists (who study such organic-walled microfossils) uses HF (hydrofluoric acid) to get rid of both carbonate and siliceous microfossils (e.g. Doher 1980). Sporopollenin therefore resist to HF, which has a pH of ca. 3. In addition to this, they are also unusually resistant to microbiological degradation (e. g. Gunnison &amp; Alexander 1975). 

They are however not resistant to oxydation, hence, probably, why we don't find more of them in the sediments. Additionally, to break sporopollenin walls (in order to study the inner side of those walls) ultrasound can be used (e. g. Lennie 1968).

"Organic-walled" doesn't mean no hard part, it just means no "mineral" hard part.

Sources:
Doher, I., 1980. Palynomorph preparation procedures currently used in the paleontology and stratigraphy laboratories, U.S. Geological Survey. Geological Survey circular, 830: 1-29.
Gunnison, D., Alexander, M., 1975. Basis for the resistance of several algae to microbial decomposition. Applied Microbiology, 29: 729-738.
Lennie, C. R., 1968. Palynological Techniques used in New Zealand. New Zealand Journal of Geology and Geophysics, 11: 1211-1221.




At the request of the OP, a little word on another group of organic-walled microfossil with a extensive, coherent Paleozoic fossil record: the Chitinozoans.  

This enigmatic group was found by Eisenack (1931) and because of their resistance to acids &amp; bases he thought they consisted of chitin, hence the name he gave them. However studies (Voss-Foucart &amp; Jeuniaux 1972; Jacob et al. 2007) showed that they do not consist of chitin or any kind of chitin-like bioproduct but of a network of kerogen with aromatic compounds. The diagenetic path that lead to this chemical composition is however unknown, meaning that we know neither what was their chemical composition when those organisms (NB: we don't know as well what their biological affinities are, though metazoan eggs seem to be a popular hypothesis, see e.g. Paris &amp; Nõlvak 1999) were alive nor how they preserved.

Additional sources:
Eisenack, A., 1931. Neue Mikrofossilien des baltischen Silurs I.
Palaeontologische Zeitschrift, 13: 74–118.
Jacob, J., et al., 2007. New insights into the chemical composition of chitinozoans. Organic Geochemistry, 36(10): 1782–1788.
Paris, F. &amp; Nõlvak, J., 1999. Biological interpretation and paleobiodiversity of a cryptic fossil group: The “chitinozoan animal”. Geobios, 32(2): 315-324.
Voss-Foucart, M.F. &amp; Jeuniaux, C., 1972. Lack of chitin in a sample of Ordovician chitinozoa. Journal of Paleontology, 46: 769–770.