The question in essence asks about a tight lower bound on the $\varphi$-function.
I believe that the best more or less universal bound is that for $n>2$, $\varphi(n)> \frac{n}{e^\gamma \log(\log n) +\frac{3}{\log(\log n)}}$ where $\gamma$ is the Euler-Mascheroni constant. The term $3/(\log(\log n))$ is there to take care of smallish $n$, and could be almost removed for large numbers, but I do not know the details.
However, crucially for your question, the term $e^\gamma \log(\log n)$ cannot be improved on.
If we look at how knowledge about the bound affects your problem, we can see that $\varphi(2n)$ can be significantly smaller than $n$ for huge $n$, so a search up to $2n$ would not be enough to rule out the existence of a solution of $\varphi(x)=n$.
The function $\log(\log n)$ grows exceedingly slowly. If you know roughly the range of values over which the search will take place, you can use the known bounds to find a suitable constant $c$ that enables you to replace $2n$ by $cn$.