We show that memory, in the form of underdamped angular dynamics, is a crucial ingredient for the collective properties of self-propelled particles. Using Vicsek-style models with an Ornstein-Uhlenbeck process acting on angular velocity, we uncover a rich variety of collective phases not observed in usual overdamped systems, including vortex lattices and active foams. In a model with strictly nematic interactions the smectic arrangement of Vicsek waves giving rise to global polar order is observed. We also provide a calculation of the effective interaction between vortices in the case where a telegraphic noise process is at play, explaining thus the emergence and structure of the vortex lattices observed here and in motility assay experiments.