As Trevor pointed out in a comment, "paradox" need not mean a contradiction in mathematics. It could mean a contradiction between a mathematical result and our intuition (e.g., the Banach-Tarski paradox), in which case it suggests either refining our intuition to incorporate the surprising mathematical knowledge or modifying the mathematical model to match our intuition more closely. In the case at hand, the situation is complicated by the presence of (at least) two ingredients in the OP's intuition that contradict the mathematical theory. The first such ingredient is the idea that it makes sense to talk about placing a point "at random" on an infinite line without specifying a probability distribution. The second is the assumption that there should be an optimal strategy for finding such a point. Even if one removes the first problem by specifying a probability distribution, and if one then uses that distribution to define the efficiency of a strategy in terms of the expectation of the time needed to find the point, there is no guarantee that this expectation is finite (for any strategy), and, even if it is finite for some strategies, there is no guarantee that there is a strategy minimizing this expectation.
Mathematicians like me will regard these problems as indicating that the OP's intuition is simply wrong and needs to be corrected in the light of the mathematics. An alternative possibility is that the OP might be able to develop a mathematical theory that incorporates the problematic intuitions and allows a precise formulation of the "paradox". I expect this alternative possibility to be very unlikely, but I won't say it's absolutely impossible.
Though it's tangential to the question, let me mention a related problem that I heard many years ago from Ingo Wegener. Fix some probability distribution on the interval $[-1,1]$, for example the one whose density function is the tent-shaped $p(x)$ given by $x+1$ for $x\leq0$ and $1-x$ for $x\geq0$. Suppose a point is chosen at random in $[-1,1]$ with respect to your fixed distribution. You are standing at $0$, you don't know where the point is, and you want to reach the point as quickly as possible by walking back and forth at unit speed. You can certainly succeed in time at most $3$ by walking all the way to one end of the interval and then, if necessary, back to the other end. So the expected time is finite for this strategy. But, for typical probability distributions, there are other strategies that do better (i.e., succeed after lower expected time). The problem is to find the optimal strategy for a given distribution and its expected time. (It's not obvious to me at the moment that the optimum must be achieved, so maybe the problem was to find the infimum, over all strategies, of the expected times and to find a sequence of strategies approaching the infimum.) At the time, Ingo told me that the problem is open even for the "tent" distribution; I don't know whether it has been solved since then.