Ok then. Here we go.

Let me write $a_n$ for the tower of $n$ nines. In fact I will show that $a_n \equiv 45289 \bmod 100000$ for every $n \geqslant 5$.

Firstly, it is immediate that $a_n \equiv 9 \bmod 10$ for every $n \geqslant 1$. (Because $a_{n-1}$ is always odd.)

Modulo $100$ we have

\[ a_n \equiv (10-1)^{a_{n-1}} \equiv 10a_{n-1} - 1 \equiv 90-1 \equiv 89 \bmod 100\]

for every $n \geqslant 2$.

In the second congruence I have used the binomial expansion and omitted all terms which are multiples of $100$. We follow the same procedure with higher powers of $10$, but greater care is needed.

Modulo $1000$ we have

\[ a_n \equiv -100\frac{a_{n-1}(a_{n-1}-1)}{2} + 10a_{n-1} - 1.\]

Now, $a_{n-1} \equiv 9 \bmod 10$. Also, $(a_{n-1}-1) \equiv 88 \bmod 100$ so $(a_{n-1}-1)/2 \equiv 4 \bmod 10$. In more detail: $a_{n-1} = 100k+89$ for some integer $k$. Then $(a_{n-1}-1)/2 = 50k+44 \equiv 4 \bmod 10$.

This gives that $a_{n-1}(a_{n-1}-1)/2 \equiv 6 \bmod 10$. So overall we get

\[ a_n \equiv -600 + 890 - 1 \equiv 289 \bmod 1000\]

for every $n \geqslant 3$.

Modulo $10000$ we have

\[ a_n \equiv 1000\binom{a_{n-1}}{3} - 100\binom{a_{n-1}}{2} + 10a_{n-1} - 1\]

To compute $\dbinom{a_{n-1}}{3} \bmod 10$ we see that

\begin{align*}

\binom{a_{n-1}}{3} &= \frac{(1000k+289)(1000k+288)(1000k+287)}{6}\\

& = \frac{(1000k+289)(500k+144)(1000k+287)}{3} \\

&\equiv 7 \cdot 9 \cdot 4 \cdot 7\\

& \equiv 4 \bmod 4

\end{align*}

Here, the first $7$ appears because $7$ is the inverse of $3$ module $10$.

We also have to compute $\dbinom{a_{n-1}}{2} \bmod 100$ which with the same process gives $89 \cdot 44 \equiv 16 \bmod 100$. Overall we get

\[ a_n \equiv 4000 - 1600 + 2890 - 1 \equiv 5289 \bmod 1000\]

for every $n \geqslant 4$.

We have yet one more round to go:

\[ a_n \equiv -10000\binom{a_{n-1}}{4} + 1000\binom{a_{n-1}}{3} - 100\binom{a_{n-1}}{2} + 10a_{n-1} - 1\]

It is left as an exercise for the reader

to check that $\dbinom{a_{n-1}}{4} \equiv 6 \bmod 10, \dbinom{a_{n-1}}{3} \equiv 64 \bmod 100$ and $\dbinom{a_{n-1}}{2} \equiv 116 \bmod 1000$. Putting all these together gives that the last 5 digits of $a_n$ are $45289$ for every $n \geqslant 5$.