Superconductors, ideally diamagnetic when in the Meissner state, can also exhibit paramagnetic behavior due to trapped magnetic flux. In the absence of pinning such paramagnetic response is weak, and ceases with increasing sample thickness. Here we show that in multiband superconductors paramagnetic response can be observed even in slab geometries, and can be far larger than any previous estimate - even multiply larger than the diamagnetic Meissner response for the same applied magnetic field. We link the appearance of this giant paramagnetic response to the broad crossover between conventional Type-I and Type-II superconductors, where Abrikosov vortices interact non-monotonically and multibody effects become important, causing unique flux configurations and their locking in the presence of surfaces.