We perform a comprehensive study of cosmological constraints on non-standard neutrino self-interactions using cosmic microwave background (CMB) and baryon acoustic oscillation data. We consider different scenarios for neutrino self-interactions distinguished by the fraction of neutrino states allowed to participate in self-interactions and how the relativistic energy density, N$_{textrm{eff}}$, is allowed to vary. Specifically, we study cases in which: all neutrino states self-interact and N$_{textrm{eff}}$ varies; two species free-stream, which we show alleviates tension with laboratory constraints, while the energy in the additional interacting states varies; and a variable fraction of neutrinos self-interact with either the total N$_{textrm{eff}}$ fixed to the Standard Model value or allowed to vary. In no case do we find compelling evidence for new neutrino interactions or non-standard values of N$_{textrm{eff}}$. In several cases we find additional modes with neutrino decoupling occurring at lower redshifts $z_{textrm{dec}} sim 10^{3-4}$. We do a careful analysis to examine whether new neutrino self-interactions solve or alleviate the so-called $H_0$ tension and find that, when all Planck 2018 CMB temperature and polarization data is included, none of these examples ease the tension more than allowing a variable N$_{textrm{eff}}$ comprised of free-streaming particles. Although we focus on neutrino interactions, these constraints are applicable to any light relic particle.