Search limit for even nontotients n is an even nontotient if n is even and Euler phi(m) = n has no solution. I am looking for a search limit L(n) depending on n. By this I mean: 
If for all k, 1 <= k <= L(n) phi(k) = n has no solution then phi(m) = n has no solution.
Is there a provable limit? (My conjecture: L(n) = 2n is sufficient.)
 A: 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$.
