In this work an exactly solvable model of N two-level systems interacting with a single bosonic dephasing reservoir is considered to unravel the role played by collective non-Markovian dephasing. We show that phase estimation with entangled states for this model can exceed the standard quantum limit and demonstrate Heisenberg scaling with the number of atoms for an arbitrary temperature. For a certain class of reservoir densities of states decoherence can be suppressed in the limit of large number of atoms and the Heisenberg limit can be restored for arbitrary interrogation times. We identify the second class of densities when the Heisenberg scaling can be restored for any finite interrogation time. We also find the third class of densities when the standard quantum limit can be exceeded only on the initial stage of dynamics in the Zeno-regime.