I spent some time working this problem and discovered the following generalization.  There's no new information here about the $2^{x-1}+5$ problem that so this is not much of an answer to that specifically.  But we can say some similar things about some similar functions.

Let $F(x)$ be a composition of functions $c$, $c^\square$, $\square + \square$, $\square \cdot \square$, $\square!$, and $\square \#$ where $\#$ is the primorial, and $c$ is a constant.  For example, we might have $F(x) = 2^{6^x + x^2} + (x \#)^2 + 3^x \cdot x - 3$, but not $F(x) = x^x$.  Let $F^k(x)$ denote the $k^\text{th}$ iterate of $F$, so for example $F^2(x) = F(F(x))$.

Lemma: $F^k(x) ~\text{mod}~ m$ is eventually periodic in $k$.

Proof: First re-write $F(x)$ so that all the bases are factored into primes, for example $F(x) = 2^{6^x} = 2^{2^x \cdot 3^x}$.  Now with $m = p^a \cdot b$ and $(p,b) = 1$, define $g_p(m) = \text{ord}_b(p)$, and observe that $p^{a+x} \equiv p^{a + (x ~\text{mod}~ g_p(m))} ~\text{mod}~ m$.  Assume as an inductive hypothesis that $F^k(x) ~\text{mod}~ n$ is eventually periodic in $k$ for all $1 \leq n < m$.  By taking all the exponents $\text{mod}$ an appropriate composition of $g$ functions we get a function eventually equal to $F(x) ~\text{mod}~ m$: for example, if $F(x) = 2^{3^x+x}$, consider $G(x) = 2^{3^{x ~\text{mod}~ g_3(g_2(m))} + x ~\text{mod}~ g_2(m)} ~\text{mod}~ m$ &mdash; then $G^k(x) ~\text{mod}~ m$ is eventually periodic in $k$ and so is $F^k(x) ~\text{mod}~ m$.  Factorials and primorials are allowed too since they are eventually equal to $0 ~\text{mod}~ m$.

Corollary: If $F(x)$ is a sum of constants to the power of functions of the more general type like $F(x) = 2^{x-1} + 5 = 2^{x-1} + 5^1$, or like $2^{7^x+x}+3$, but not like $F(x) = 2^x + x$, or in other words if it has no polynomial additive terms, then $F^k(x) ~\text{mod}~ m$ is eventually fixed for all $m$.  So I think we're likely to have $F^k(x) \vert F^{k+1}(x)$ with other functions of this type for most values of $k$ and $x$, since "eventually" is not usually very long and $F^k(x)$ only has a few chances to be divisible by $p$ before it's fixed as a divisor for all larger $k$.