This problem is analogous to the "ultraviolet catastrophe" in the pre-quantum understanding of black-body radiation. There, because one did not take into account the discrete character of radiation, the total energy emitted by a black-body was divergent. Planck came along and remedied the situation by noting that photons were emitted in discrete packets rather than the previous assumption that all frequencies occurred in the radiation.
Similarly, as @Johannes noted in his answer, the calculations which lead to the prediction that a black hole radiates at a temperature $T \propto 1/M$ are valid only for macroscopic black holes. As and when, we understand how the discrete character of spacetime modifies this dependence, will we be able to answer this question. The simplest thing to do is to guess that such corrections will modify the temperature-mass dependence to be of the form:
$$ T \propto \frac{1}{M + M_O} $$
where $M_O$ is the minimal size a black-hole can attain, leading to a finite maximum temperature that a system containing a decaying black hole can attain $T_{max} \sim 1/M_O$. The conjecture would be that a black-hole decays until we are left with a flat background populated by a gas of these black-hole quanta of mass $M_O$ and temperature $T_{max}$.
Of course, this is all very hand-wavy.
Edit: A generalization of the above approach is to postulate that the exact form of the dependence of $T_{max}$ on $M$ is given by some function $f(M/M_O)$ which tends to $ 1/M $ in the limit $M/M_O \rightarrow \infty$.