Let $p$ be a prime. For how many elements $x$ of $\{0,1,\dotsc,p-1\}$ can it be the case that $$2^{2^{2^{2^x}}} = x \mod p?$$
In particular, can you find a simple proof (or, even better, several simple proofs!) of the fact that this can happen only for $< \epsilon\cdot p$ elements $x$ of $\{0,1,\dotsc,p-1\}$?
(Assume, if needed, that $2$ is a primitive root of $\mathbb{Z}/p\mathbb{Z}$.)
The aim of this answer is to sketch a proof of the fact that there are at most $\epsilon p$ solutions to $2^{2^{2^x}} = x \mod p$. The original question -- namely, to show the same for $2^{2^{2^{2^x}}} = x \mod p$ -- remains open for now.
Suppose there were $\gg p$ (meaning: $> \epsilon p$ for some fixed $\epsilon>0$) solutions to $2^{2^{2^x}} = x \mod p$. Then there would have to be a bounded constant $k$ such that $x$ and $x+k$ are both solutions for $\gg p$ values of $x$. For all such $k$,
$$2^{2^{2^x}}+k = x+k = 2^{2^{2^{x+k}}} = 2^{2^{2^k 2^x}} = 2^{(2^{2^x})^{2^k}} \mod p.$$
Writing $y$ for the integer in $\{0,1,...,p-2\}$ congruent to $2^{2^x} \mod p-1$, we obtain that there are $\gg p$ elements $y$ of $\{0,1,...p-2\}$ (or $\{0,1,...,p-1\}$) such that
$$2^{y^{2^k}} = 2^y + k \mod p.\;\;\;\;\;\;\;\;\; (*)$$
By the same reasoning as before, this implies that, for any $r$, there is an $(r+1)$-tuple of distinct constants $l_0=0,l_1, l_2,...,l_r$ such that, for $\gg p$ elements $y$ of $\{0,1,...p-1\}$, (*) is true for every $y+l_i$, $0\ll i \ll r$. Now, set $r = 2^k$. The $r+1$ polynomials
$$(y+l_i)^{r},\;\;\;\;\;\; 0\leq i\leq r$$
are linearly independent (because this is true over $\mathbb{Z}$ or $\mathbb{R}$: Vandermonde matrix is non-singular), but, since they each have r+1 coefficients, they and any other polynomial in y -- in particular, the polynomial y -- must be linearly dependent. Hence, there are (bounded integer constants) $c$ (not zero) and $c_i$, $0\leq i\leq r$, not all of them zero, such that $c y = \sum_{0\leq i\leq r} c_i (y+l_i)^{2^k} = 0$. Therefore,
$$\prod_{0<=i<=r} (2^{(y+l_i)^{2^k}})^{c_i} = 2^{\sum_{0<=i<=r} c_i (y+l_i)^{2^k}} = 2^{c y} \mod p,$$
and so
$$\prod_{0<=i<=r} (2^y + k)^{c_i} = 2^{c y} \mod p.$$
Setting $z = 2^y$, we see we have an equation
$$(z + k)^{\sum_{0<=i<=r} c_i} = z^c \mod p.\;\;\;\;\;\;\;\; (**)$$
supposedly satisfied by $\gg p$ elements of $\{0,1,...p\}$. Let $C = \sum_{0<=i<=r} c_i$. If $C\geq 0$, (**) is just the equation
$$(z+k)^C = z^c \mod p;$$
if $C<0$, (**) is equivalent to the equation
$(z+k)^C z^c = 1 \mod p$.
In either case, we have an equality between two identical polynomials. Such an equality ($\mod p$) can have at most a bounded number of solutions. Contradiction.
Can you provide a simpler proof of the above? Can you adapt it to $2^{2^{2^{2^x}}} = x \mod p$?
Your argument for three exponentials can be simplified a bit by using the multiplicative version of van der Corput instead of the additive version. Specifically, if your equation $$2^{y^{2^k}} = 2^{y} + k \quad(\ast)$$ has many solutions then there is some bounded $l>1$ such that there are many pairs of solutions $y,ly$, and for any such pair we must have $z=2^y$ solving $$(z+k)^{l^{2^k}} = z^l + k,$$ which of course has a bounded number of solutions. (Equivalently, write the equation in terms of $y' = 2^x$ instead of $y=2^{2^x}$ and apply additive vdC.)
If we're being more careful then we should define $f:\mathbf{Z}/p\mathbf{Z}\to\mathbf{Z}/p\mathbf{Z}$ by $f(x) = 2^{\bar{x}}$, where $\bar{x}$ is the representative of $x$ satisfying $0\leq\bar{x}<p$. We're really interested in solutions to $fff(x)=x$, but using the "cocycle" relations $$f(x+y) = \begin{cases} f(x)f(y)&\text{or}\\f(x)f(y)/2,\end{cases}$$ and $$f(kx) = f(x)^k/c\text{ for some bounded }c=c_x,$$ one can reduce the problem to counting solutions to a bounded number of equations like $(\ast)$ to which the same argument applies. (I'm sure you, Helfgott, already had something like this in mind, but others may have wondered how the discontinuities could be handled.)
The equation $ffff(x)=x$ is certainly daunting. The analogue of $(\ast)$ here is, for $k=1$, $$2^{2^{y^2}} = 2^{2^y} + 1.\quad(\ast\ast)$$ Obviously $y$ and $-y$ are never both solutions to this equation, but this does not prove a $1-\epsilon$ bound because really we care about solutions $y$ to either $ff(y^2)=ff(y)+1$ or $ff(y^2/2)=ff(y)+1$, and we could well have $-y$ a solution to one whenever $y$ is a solution to the other. I don't see how to make any real progress.
[Comment from before I understood the intended question, and I thought we were counting integers $x$ in the range $0\leq x<p$ whose quadruple exponential, evaluated in $\mathbf{Z}$, is equivalent to $x\pmod{p}$: For generic $p$, the number $p-1$ will have many prime factors, which implies that $(\mathbf{Z}/(p-1)\mathbf{Z})^\times$ will surject onto $(\mathbf{Z}/2\mathbf{Z})^m$ for some large $m$. Thus not many elements of $(\mathbf{Z}/(p-1)\mathbf{Z})^\times$ are of the form $y^2$, so not many elements $x$ of $\mathbf{Z}/p\mathbf{Z}$ are even of the form $2^{y^2}$, let alone of the form $2^{2^{2^z}}$ for some integer $z \equiv x\pmod{p}$.]
(Later note: This argument only works when $2$ has multiplicative order $p-1$ (mod $p$), but may give some insight to others for the general case).
This isn't really an answer, and I'm in two minds about posting it, but since no one else apart from the OP has answered, here goes: assuming that $2$ generates $A = (\mathbb{Z}/p\mathbb{Z})^{\times}$, the map $f : x \to 2^{x}$ is a bijection from $A$ to itself (where obviously $2^{x}$ is read (mod $p$) ). The question seems to amount to asking that $f$ has fewer than $\varepsilon p$ short cycles when written as a permutation ( where the meaning of short depends on the height of the tower of iterated exponentials you choose).
In trying to address this, I find it difficult to know how to generalise the question to a general finite Abelian group $G.$ If we have an arbitrary permutation $f$ of the elements of $G$, there is no a priori reason to expect $f$ to have few short cycles, (although working probabilistically, a random permutation is relatively unlikely to have short cycles)so the interaction between the additive and multiplicative structure of $\mathbb{Z}/p\mathbb{Z}$ must be playing a role. Furthermore, there does come a point at which $f^{n}$ will have plenty of fixed points, for example when $n$ is the order of the permutation $f$.
So what are the distinguishing features of the map $f$? Note that $f$ has the property that $f(x)f(-x) = 2.$ More generally, we have $f(x+y) = f(x)f(y)$ if $0 < x \leq y < x+y < p$ and $2f(x+y) = f(x)f(y)$ when $0 < x \leq y < p < x+y$. Note in particular that $x^{p-1}-1$ is a factor of $f(x)f(-x) -2.$
The question suggests another: what is the smallest value of $m$ such that $f$ has more than $\varepsilon p$ cycles of length $m?$ One way to attack that would be to show the existence of a cycle of almost maximal possible length. I don't know if there always is such a cycle.
