To paraphrase the problem: The adversary selects some natural number and provides you with an oracle which will tell you whether a number of your choice is greater or less than the secret number. You want to find the secret in the fewest possible tries.
The first question to consider is what a reasonable complexity measure would be. Average complexity is out because it would depend on the probability distribution with which the adversary selects various number, and there's no "natural" probability distribution on $\mathbb N$ we can assume in default of better information.
The only thing that seems to make good sense is considering how the running time of an algorithm grows as a function of the adversary's unknown number. We could consider ordinary asymptotic growth here (that is, ignoring constant factors), but since "number of questions to the oracle" is a well-defined unit of complexity, we can be slightly more precise and only ignore constant terms.
The counting argument Thomas Andrews presents shows that any correct algorithm must use at least $\log_2 k \pm c$ questions in the limit to locate the number $k$, for some constant $c$.
The doubling-then-binary-search algorithm you suggest will use $2\log_2 k \pm c$ questions in the limit -- namely first $\log_2 k$ questions to determine the size of $k$ and then $\log_2 k$ questions the discover its lower-order bits. The constant $c$ depends on how large your initial guess is; you can get as large a negative $c$ simply my making your initial guess in the doubling phase large. (This is why we might as well ignore constant terms in the number of questions; they can be traded for more time spent in a bounded initial range of $k$s).
What's the best $a$ such that there's an algorithm that uses at most $a\log_2 k + c$ questions in the limit? So far we have the bounds $1\le a\le 2$; can we narrow down that interval? I don't know.