Thanks at below for the nice solution. I was able to fix my mistake (I assumed $p|\Phi_p(a)$). Here is a write up using Cyclomatic Polynomials (more or less identical to below but I think it helps to motivate a lot of the steps).

. Case 1: $a\equiv 1,2 \pmod{4}$ Choose a prime $p\equiv 7 \pmod{12}$ such that $p>a$ and consider the polynomial $\Phi_{p}(a)$. Notice that $\Phi_{p}(a)\equiv 3 \pmod{4}$ so there must exist a prime $q$ such that $q\equiv 3 \pmod 4$ and $q|\Phi_{p}(a)$. As $p\nmid a^p-1$ we must have that $q\neq p$ so $q\equiv 1 \pmod{p}$. As neither $p+1$ or $2p+1$ is prime, it follows that $p<\frac{q-1}{2}$. Since $q|a^p-1$, $q$ is such an integer. By choosing a prime $p$ larger than all previous $q$ (which exists by Dirichlet's Theorem) we can generate infinitely many new $q$. Case 2: $a\equiv 31 \pmod{60}$ Chose a prime $p\equiv 11 \pmod{12}$ such that $p>a^2$ and consider the polynomial $\Phi_{2p}(a)$. Notice that $\Phi_{2p}(a) \equiv 3 \pmod{4}$ so there must exist a prime $q$ such that $q\equiv 3 \pmod{4}$ and $q|\Phi_{2p}(a)$. As $p \nmid a^{2p}-1$ we must have $q\equiv 1 \pmod{2p}$. As $2q+1$ and $4q+1$ are both not prime, it follows that $2p>\frac{q-1}{2}$. Since $q|a^{2p}-1$, $q$ is such an integer. By choosing a prime $p$ larger than all previous $q$ (which exists y Dirichlet's Theorem) we can grantee infinitely many new $q$.

Lemma: There are infinitely many primes like $p$ of the form $4k-3$ for which $2p+1$ is a composite number. Proof: Assume otherwise for contradiction. Let $p_1<p_2<\ldots<p_t$ be all primes satisfying the condition and $p$ be a prime larger than $p_t$. Now consider the sequence $(a_n)_{n=0}^{\infty}$ by the following way: $$a_0=p , a_n=2a_{n-1}+1$$Note that each term of this sequence has to be a prime by our assumption. You can easily show that $a_n=2^np+2^n-1$ by induction, thus by Fermat's theorem, we have that $a_{p-1}$ is divisible by $p$. This is a contradiction and hence this lemma is proved. Let $d$ be a prime of the form $4k-1$ such that $2d+1$ is a composite number. There are infinitely many of them indeed. We consider two cases: Case 1: $a\equiv 1,2\pmod{4}$ Then we choose $d$ such that $d\nmid a-1$. Hence $gcd(\frac{a^d-1}{a-1},a-1)=1$. Further $\frac{a^d-1}{a-1}$ is of the form $4k-1$ and all of its prime factors are of the form $2sd + 1$ since $d$ is the order. Hence, there is a prime $p$ of the form $4k-1$ such that $p\mid a^d-1, gcd(p,a-1)=1$ and then $p=2rd+1$ where $r\ge 2$ since $2d+1$ is composite. Further, distinct $d$ will determine distinct $p$ since $gcd(a^m-1,a^n-1)=a^{gcd(m,n)}-1$ and note that $d<\frac{p-1}{2}$. Thus in this case we are done! Case 2: $a\equiv 3\pmod{4}$ Let $d$ be a prime number of the form $4k-1$ such that $gcd(d,a^2-1)=1$ and $2d+1$ is a composite. Then $\frac{a^{2d}-1}{a^2-1}$ would be of the form $4k-1$ and hence, would have a prime divisor $p$ of the form $4k-1$ such that $gcd(p,a^2-1)=1$. Further, $p=2sd+1$ and since $s\ge 2$ we have $2d<\frac{p-1}{2}$. Thus we are done $\square$