You are correct that $3$ and $11$ are the only solutions.
If $p$ is prime then $100^p\equiv 100\pmod p$ by Fermat's little theorem. So $100^p\equiv1\pmod p$ would mean $100\equiv1\pmod p$, i.e., $p$ divides $100-1=99$. The prime factorization of $99$ is $3^2\times11$; i.e., the prime factors of $99$ are $3$ and $11$. So if $100^p\equiv1\pmod p$ then $p\in${$3,11$}.
The modulus $\ p\ $ must be larger than $\ \max\left(m_1^*, m_2^*, m_3^*\right)\ $, and $\ \left(m_1^*-m_2^*\right) \left(m_3^\ -m_2^\ \right)\equiv a \left(m_1-m_2\right) \left(m_3^\ -m_2^\ \right)\equiv$$\left(m_1^\ -m_2^\ \right) \left(m_3^*-m_2^*\right) \pmod{p}\ $, so $\ p\ $ must divide $\ \left(m_1^*-m_2^*\right) \left(m_3^\ -m_2^\ \right)-\left(m_1^\ -m_2^\ \right) \left(m_3^*-m_2^*\right)\ $. To be useable as cipher, the plain messages must also be restricted to a range of at most $\ p\ $ integers whose remainders mod $\ p\ $ are distinct, and $\ p\ $ must be larger than the largest remainder mod $\ p\ $ of that set of integers. Typically, the set would be $\ \mathbb{Z}\cap[0,p-1]\ $, but here I'll assume you don't know what it is.
In any case, $\ p\ $ must be a divisor of $\ \left(m_1^*-m_2^*\right) \left(m_3^\ -m_2^\ \right)-\left(m_1^\ -m_2^\ \right) \left(m_3^*-m_2^*\right)\ $ that exceeds $\ \max\left(m_1^*, m_2^*, m_3^*\right)\ $, of which there will only be a finite number. For each such possible value of $\ p\ $ you can then solve the linear equations for $\ a\ $ and $\ b\ $, provided that $\ gcd\left(m_1,m_2,m_3,p\right)=1\ $. If this is the case, let $\ \gamma=\gcd\left(m_1,m_2, m_3\right)\ $. Then $\ \gcd\left(\gamma,p\right)=1\ $, and you can find integers $\ k_1,k_2,k_3\ $ such that $\ k_1m_1+k_2m_2+k_3m_3=\gamma\ $, and
\begin{align}
a&=\gamma^{-1}\left(k_1m_1^*+k_2m_2^*+k_3m_3^*-\left(k_1+k_2+k_3\right)b\right)\pmod{p}\\
b&=m_1^*-am_1\pmod{p}\ .
\end{align}
If there is more than on one potential solution satisfying these conditions, there might still be some of them which fail to satisfy at least one of the congruences
$$
m_i^*\equiv am_i+b\pmod{p}\ ,
$$
in which case, it can be eliminated as a possibility.
Example:
Suppose $\ m_1=15, m_2=17,m_3=22, m_1^*=7,m_2*=429, m_3^*=484\ $.Then
\begin{align}
\left(m_1^*-m_2^*\right) \left(m_3^\ -m_2^\ \right)-\left(m_1^\ -m_2^\ \right) \left(m_3^*-m_2^*\right)=-2000
\end{align}
The only (positive) divisors of $\ -2000\ $ which exceed $\ \max\left(m_1^*,m_2^*,m_3^*\right)=$$484\ $ are $500$, $1000$, and $2000$, one of which must be the value of $\ p\ $. Also, $\ \gcd\left(m_1,m_2, m_3\right)=$$\gcd\left(15,17,22\right)=$$1=8\cdot15-7\cdot15\ $. Therefore
\begin{align}
a&\equiv8m_1^*-7m_2^*-b\pmod{p}\\
&\equiv-3289 \pmod{p}\\
&\equiv711 \pmod{p}\\
b&\equiv m_1^*+3289m_1 \pmod{p}\\
& \equiv 49342 \pmod{p}\\
& \equiv 1342\pmod{p}\ ,
\end{align}
because all the possible values of $\ p\ $ are divisors of $2000$.
Thus, the only possible solutions are
\begin{align}
p&=500, a=211, b=342\\
p&=1000, a=711, b=342\\
p&=2000, a=711, b=1342\ .
\end{align}
But \begin{align}
711m_3+1342\hspace{-0.5em}\pmod{2000}&=711m_3+342\hspace{-0.5em} \pmod{1000}\\
&=984\\
&\ne484=m_3^*\ ,
\end{align}
so the only possible solution is $\ p=500, a=211,$ and $\ b=342\ $.
Thus it is certainly sometimes possible to recover $\ p,a\ $, and $\ b\ $ uniquely with only three matched plain and cipher pairs, but it is certainly also possible that there will not be a unique solution for such a small number of matched pairs.
Best Answer
I posted a proof here that RSA is a bijective map from $\mathbb{Z}_n$ to itself, provided that $(\phi(N),e) =1$, and where the message space is the set of classes modulo $N$, the modulus.
So if we assume (as we must) that we are working in that message set, the RSA mapping has an inverse (using the exponent $d$ as described) and is in particular injective.
I also use the CRT, but why not? It's a basic tool in number theory. It's not "complicated".