Is there an asymptotically optimal algorithm for unbounded search?
The basic observation is:


  Lemma. Suppose $a_s$ is a nondecreasing sequence of integers. There exists a strategy which uses $a_s$ queries when the answer is $s$ if and only if
  $$ \sum_{s=1}^\infty 2^{-a_s} \leq 1. $$


In one direction, consider any strategy. For each $s$, let $w_s$ be the sequence of answers to queries made by the strategy. No word in the collection $\{w_s\}$ is a prefix of another, and so the collection forms a prefix code. The lengths $a_s = |w_s|$ therefore satisfy Kraft's inequality, $\sum_{s=1}^\infty 2^{-a_s} \leq 1$.

In the other direction, let us suppose that $\sum_{s=1}^\infty 2^{-a_s} \leq 1$. Decrease the $a_s$ if need be (while keeping them nondecreasing) so that $\sum_{s=1}^\infty 2^{-a_s} = 1$ (this is always possible); we can restore the original values later by asking dummy questions. Since the $a_s$ are nondecreasing, there is an index $S$ such that
$$ \sum_{s=1}^S 2^{-a_s} = \sum_{s=S+1}^\infty 2^{-a_s} = \frac{1}{2}. $$
The first question asked by the strategy is "$s \leq S$?". If the answer is affirmative, recurse on $a_1-1,\ldots,a_S-1$; otherwise, recurse on $a_{S+1}-1,\ldots$. The left recursion is different from the right recursion, since $a_1-1,\ldots,a_S-1$ is finite; but a similar argument works, with a base case of $a_1 = 0$, in which case no more questions need be asked. $\quad \square$

Given the lemma, we have reduced the question to the topic of the paper universal codes of the natural numbers, in which it is shown that no optimal strategy exists (in a certain reasonable sense formalized in the paper).