We analyze a microscopic decoherence model in which the total system is described as a spin gas. A spin gas consists of N classically moving particles with additional, interacting quantum degrees of freedom (e.g., spins). For various multipartite entangled probe states, we analyze the decoherence induced by interactions between the probe and environmental spins in such spin gases. We can treat mesoscopic environments (≈105 particles). We present results for a lattice gas, which could be realized by neutral atoms hopping in an optical lattice, and show the effects of non-Markovian and correlated noise, as well as finite-size effects.