Here's a somewhat clunky characterization that deals with the $\gcd(a, n) \ne 1$ case. I think you can probably say nicer things if you only want a sufficient condition.
Let $a, n$ not necessarily coprime and $b$ be arbitrary. For convenience, write $b = qn + r$ with $0 \le r < n$, so that the condition $a^b \equiv a^{b \bmod n} \pmod{n}$ is equivalent to $a^{qn+r} \equiv a^r \pmod{n}$. Let $n = p_1^{k_1} \cdots p_s^{k_s}$ be the prime factorization of $n$. By the Chinese remainder theorem, the desired congruence then holds if and only if $a^{qn+r} \equiv a^r \pmod{p_i^{k_i}}$ for all primes $p_i \mid n$.
Now fix a prime $p \mid n$, and consider when $$ a^{qn+r} \equiv a^r \pmod{p^k} $$ holds. First, if $\gcd(a, p) = 1$, then by the same argument as in the OP, the congruence holds iff $\mathrm{ord}_{p^k}(a) \mid q n$. Otherwise, if $\gcd(a, p) \ne 1$, then we have $p \mid a$. Notice that the displayed congruence is equivalent to $a^{qn+r} - a^r \equiv 0 \pmod{p^k}$, or $p^k \mid a^r(a^{qn} - 1)$. Since $p \mid a$, we see that $p \nmid a^{qn} - 1$ unless $q = 0$, i.e., unless $b < n$. Hence $p^k \mid a^r(a^{qn} - 1)$ if and only if either $p^k \mid a^r$ or $b < n$ in this case.
This proves
Theorem. Assume $b \ge n$ so that the desired congruence is nontrivial. Then $a^b \equiv a^{b \bmod n} \pmod{n}$ if and only if, for all primes $p \mid n$ with multiplicity $k$, either
- $p \nmid a$ and $\mathrm{ord}_{p^k}(a) \mid (b - b \bmod n)$, or
- $p \mid a$ and $p^k \mid a^{b \bmod n}$.
which can be rephrased as
Corollary. Assume $b \ge n$ so that the desired congruence is nontrivial. Then $a^b \equiv a^{b \bmod n} \pmod{n}$ if and only if $\mathrm{ord}_m(a) \mid (b - b \bmod n)$ and $\frac{n}{m} \mid a^{b \bmod n}$, where $m$ is the product of the prime powers in $n$ coprime to $a$.
Note that in the case where $a$ and $n$ are coprime, this characterization reduces to the one stated in the OP, so in some sense it is a natural generalization.
