Large language models (LLMs) have shown strong performance in many downstream reasoning benchmarks. However, recent studies have pointed to memorization, rather than generalization, as one of the leading causes for such performance. LLMs, in fact, are susceptible to content variations, demonstrating a lack of robust symbolic abstractions supporting their reasoning process. To improve reliability, many attempts have been made to combine LLMs with symbolic methods. Nevertheless, existing approaches fail to effectively leverage symbolic representations due to the challenges involved in developing reliable and scalable verification mechanisms. In this paper, we propose to overcome such limitations by generating high-quality symbolic reasoning trajectories at scale through Monte Carlo estimation, which are then employed via fine-tuning methods to improve logical reasoning and generalization. Our results on benchmarks such as FOLIO and LogicAsker show the effectiveness of the proposed method with large gains on frontier and open-weight models. Moreover, additional experiments on claim verification reveal that fine-tuning on the generated symbolic reasoning trajectories enhances out-of-domain generalization, suggesting the potential impact of symbolically-guided process supervision in alleviating the effect of memorization on LLMs' reasoning.