We present our findings of a large-scale screening for new synthesizable materials in five M-Sn binaries, M = Na, Ca, Cu, Pd, and Ag. The focus on these systems was motivated by the known richness of M-Sn properties with potential applications in energy storage, electronics packaging, and superconductivity. For the systematic exploration of the large configuration space, we relied on our recently developed MAISE-NET framework that constructs accurate neural network interatomic potentials and utilizes them to accelerate ab initio global structure searches. The scan of over two million candidate phases at a fraction of the typical ab initio calculation cost has uncovered 29 possible intermetallics thermodynamically stable at different temperatures and pressures (1 bar and 20 GPa). Notable predictions of ambient-pressure materials include a simple hP6-NaSn2 phase, fcc-based Pd-rich alloys, tI36-PdSn2 with a new prototype, and several high-temperature Sn-rich ground states in the Na-Sn, Cu-Sn, and Ag-Sn systems. Our modeling work also involved ab initio (re)examination of previously observed M-Sn compounds that helped explain the entropy-driven stabilization of known Cu-Sn phases. The study demonstrates the benefits of guiding structure searches with machine learning potentials and significantly expands the number of predicted thermodynamically stable crystalline intermetallics achieved with this strategy so far.