The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we happily go from
$\qquad T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n)$
to
$\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n)$
considering only $n=2^k$. We assure ourselved that this step is valid -- that is, $T \in \Theta(T')$ -- because $T$ behaves "nicely". In general, we assume $n=b^k$ for $b$ the common denominator.
It is easy to construct recurrences which do not allow this simplification by using vicious $f$. For example, above recurrence for $T\,$/$\,T'$ with
$\qquad f(n) = \begin{cases} 1 &, n=2^k \\ n &, \text{else} \end{cases}$
will yield $\Theta(n)$ by using the Master theorem in the usual way, but there is clearly a subsequence that grows like $\Theta(n \log n)$. See here for another, more contrived example.
How can we make this "nicely" rigorous? I am quite certain that monotonicity is sufficient, but not even the simple Mergesort recurrence is monotone; there is a periodic component (which is dominated asymptotically). Is it enough to investigate $f$, and what are necessary and sufficient conditions on $f$ that ensure the Master theorem works?