It is well known that temperature solutions of the Implicit Monte Carlo (IMC) equations can exceed the external boundary temperatures, a violation of the “maximum principle.” Previous attempts to prescribe a maximum value of the time-step size Δt that is sufficient to eliminate these violations have recommended a Δt that is typically too small to be used in practice and that appeared to be much too conservative when compared to the actual Δt required to prevent maximum principle violations in numerical solutions of the IMC equations. In this paper we derive a new, approximate estimator for the maximum time-step size that includes the spatial-grid size Δx of the temperature field. We also provide exact necessary and sufficient conditions on the maximum time-step size that are easier to calculate. These explicitly demonstrate that the effect of coarsening Δx is to reduce the limitation on Δt. This helps explain the overly conservative nature of the earlier, grid-independent results. We demonstrate that the new time-step restriction is a much more accurate predictor of violations of the maximum principle. We discuss how the implications of the new, grid-dependent time-step restriction can affect IMC solution algorithms.