I present the solution I find during the contenst. Assume for the sake of contradiction, that problem statement is false. So take $t$ as the minimal positive integer that does not appear on the sequence. So there must exist $N \in {\mathbb{Z}}_{>0}$ such that $\{ 1,2, \dots , t-1 \} \subset \{a_0, a_1,a_2, \dots , a_N \}.$ Key Step: Say an positive integer $l$ is k-good if $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\bullet$ $l \equiv 0 \pmod {p_1p_2 \dots p_{k-1}}$ $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\bullet$ $l \equiv 1\pmod {p_k}$ where $k$ is an positive integer and $p_i$ is the i-th prime number. Note that $a_n$ cannot be a k-good number for any $n>N;$ else we would have $a_{n+1} = t$ (as $p_k =p(a_n) \mid ({a_n}^t -1)$ and $1,2, \dots t-1$ have already appeared) which cannot happen. In particular, there are finitely many k-good numbers that appears in the sequence. In order to proceed, we first prove the following bound for $p()$ Lemma: $p(n) <D \log n$, for some constant $D$ for all $n$ .

Now take sufficiently large constants $P,Q$. As ${\{a_n\}}_{n\ge 0}$ passes through each positive integer at most once, there must exist an $n$ satisfying: $~~~~~~~~~~~~~~\bullet n> P;$ $~~~~~~~~~~~~~~\bullet a_n > Q;$ $~~~~~~~~~~~~~~\bullet a_{n+1}> a_n,;$ Now let $q = p(a_n).$ Take $L$ as an positive integer larger than the quantity of good numbers in the sequence. Now take $k$ such that $p_k = p(q-1).$ Note that by the choice of $k$ and the Lemma we must have $~~~~~~~~~~~~~~ p_k \nmid q-1$ $~~~~~~~~~~~~~~ L \cdot lcm( p_1,p_2, \dots p_k ,q-1)= L \cdot p_k \cdot (q-1) < a_n$ where the last inequality holds because of Lemma ( as $q<D \cdot \log(a_n)$ and $p_k < \log(q-1) < D\log (\log a_n)$, and so the inequality must hold when taking $a_n$ large enough.) Note that the two condition above implie by Chinese Remainder Theorem that there must exist at least $L$ solutions smaller than $a_n$ to $~~~~~~~~~~~~~~ x \equiv 0 \pmod{ lcm (p_1, p_2, \dots, p_{k-1}, q-1)}$ $~~~~~~~~~~~~~~ x \equiv 1 \pmod {p_k}$ As all of these numbers are k-good and there are less than $L$ k-good numbers in the sequence, one of these numbers have not appeared in the sequence, say $c$ has not appeared in the sequence and satisfies all the above conditions. Note that as $q-1 \mid c,$ we must have $q \mid {a_n}^c -1$ and so $a_{n+1} \le c \le a_n$, which contradicts the choice of $n.$ And we are done.

Solution with no analysis flavour by my friend Joao Guilherme, aka jooj: Suppose that the problem statement is false and let $p_1, p_2, \dots$ the prime numbers in order. Claim: For every prime $q$, there are only finitely many $m$ satisfying $p(a_m) = q$. $\textit{Proof.}$ Suppose that not and let $\{ a_{b_n}\}_{n=1}^\infty$ be the whole and increasing subsequence of $\{ a_n \}_{n=1}^\infty$ such that $p(a_{b_i}) = q~\forall i$, for such prime $q$. Note that if a multiple of $q-1$, say $(q-1)l$, doesn't appear on the sequence, looking at $a_{b_{m}}$ for $m$ large enough we have that $a_{b_{m}+1} > (q-1)t$ and $q \mid a_{b_m}^{(q-1)t}-1$, contradiction by the definition. Hence, all multiples of $q-1$ appears on the sequence. To finish the claim, if $q=p_{m}$, we have that $x_j := p_1p_2 \dots p_{m-1}(p_m-1)j$ is on the sequence for all $j \in \mathbb{N}$. Take the subsequence of $x_j$ such that $x_j \equiv 1 \pmod{p_m}$, i.e, $j$ being a certain fixed value in$\pmod{p_m}$ . What happens is that, by definition, the term right after $x_j$ is the least integer that doesn't appeared yet. As this construction gives infinitely many $j$, we have that every positive integer appears on the sequence, contradicting our hypothesis. $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \blacksquare$ So by the claim, it directly follows that for each $p_m$ there exists $n_0$ such that $\forall n > n_0$ is true that $p_1p_2 \dots p_m \mid a_n$, as $m$ varies on positive integers. Take $k$ such that $p_1 p_2 \dots p_m \mid a_k$; $p_{m+1} \nmid a_k$ and $p_1 \dots p_m p_{m+1} \mid a_{i}$ for all $i>k$ and certain $m$. So $a_k ^{a_{k+1}} \equiv 1 \pmod{p_{m+1}}$. If $a_{k+1} = p_1 p_2 \dots p_{m+1}l$, using lil fermat's we have that $a_k^{(p_1 p_2 \dots p_m l)i} \equiv 1 \pmod{p_{m+1}}$ for all $i = 1, 2, \dots p_{m+1}-1$, so all of those $y_i := (p_1 p_2 \dots p_m l)i$ must appear on the sequence due definition. But in fact one of those $i$ makes $y_i \equiv 1 \pmod{p_{m+1}}$ by the existence of it's inverse, so the next term of $y_i$ on the sequence is the least integer that doesn't appeared yet, since $p(y_i) = p_{m+1}$. As we can do this for every $m$ such that $p_m$ is the least prime to arrives in the sequence on it's gap break, i.e, infinitely many times (since there's no way such that infinitely many primes can arrive together), we have that all positive integers are on the sequence. $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \blacksquare$

Solved with @MathLuis Pretty much same as above The idea is to find a condition that forces the smallest number that haven't appeared yet in the sequence to appear (maybe it sounds a bit confusing), anyway let Definition: A number $x$ is said to be nice, if it is $k$-nice, for some $k > 0$. Definition: A number $x$ is $k$-nice if it satisfies the following system of equations \begin{align*} x &\equiv 0 \mod p_1p_2 \dots p_{k-1} \\ x &\equiv 1 \mod p_k \end{align*}where $p_k$ is the $k$-th prime. Notice that the problem statement is equivalent to prove that $\{ a_n\}_{n > 0}$ contains infinitely many nice numbers. Notice that $p(x) = \mathcal{O}(\log(x))$, because the product of the first $k-1$ primes (buzzword: primorial) will be be bounded below by $\left(\frac{\frac{p_k}{\log p_k}}{e}\right)^{\frac{p_k}{\log p_k}}$ (this is true due to an elementary version of PNT and some loose estimates of factorials) Now, assume that the number of nice numbers in the list is finite. Pick big $a_n$ with $a_n < a_{n+1}$, and notice that the number of $p(p(a_n) - 1)$-nice numbers that are also multiples of $p(a_n) - 1$ and smaller than $a_n$ is bounded below by $\frac{a_n}{\log(a_n)\log(\log(a_n))}$, therefore we can find an $x$ smaller than $a_n$ and not in the sequence satisfying the necessary properties. This gives a contradiction because $p(a_n) \mid a_n^{x} - 1$, therefore $a_{n+1} \leq x < a_n$