Solution:
The idea is that most perfect powers are squares. If $a_{n}=x^{2}$ and $a_{n+1}=(x+1)^{2}$, then $a_{n+1}-a_{n}=2x+1$. Note that $9999 \mid 2x+1$ is equivalent to $x \equiv 4999 \pmod{9999}$. Hence we will be done if we can show that there exist infinitely many $x \equiv 4999 \pmod{9999}$ such that there are no perfect powers strictly between $x^{2}$ and $(x+1)^{2}$.

Assume otherwise, so that there exists a positive integer $N$ such that: for $x \equiv 4999 \pmod{9999}$ and $x \geq N$, there is a perfect power $b_{x}^{e_{x}}$ ($e_{x} \geq 2$) between $x^{2}$ and $(x+1)^{2}$. Without loss of generality, we can take $N$ to be $\equiv 4999 \pmod{9999}$. Note that $x^{2}$ and $(x+1)^{2}$ are consecutive squares, hence $e_{x}$ is odd, and thus $e_{x} \geq 3$. Let $t_{n}$ be the number of odd perfect powers that are at most $n$.

By tallying the $b_{x}^{e_{x}}$ up (clearly they are all distinct), for any $m \geq 1$ we have at least $m$ perfect odd powers between $1$ and $(N+9999m)^{2}$, so that
$$t_{(N+9999m)^{2}} \geq m$$
In particular, for large enough $n$ we have
$$t_{n} \geq \frac{\sqrt{n}}{10000}$$
Now, if $x^{f} \leq n$ then $x \leq \sqrt[f]{n}$. Also, $n \geq x^{f} \geq 2^{f}$ so $f \leq \log_{2}(n)$. So we have
$$t_{n} \leq \sum_{i=3}^{\log_{2}(n)} \sqrt*{n} \leq \log_{2}(n) \sqrt[3]{n}$$
Combining with the previous inequality, we have
$$\sqrt[6]{n} \leq 10000 \log_{2}(n)$$
for all large enough $n$. However, this inequality is false for all large $n$, contradiction. Therefore the problem statement holds.