Q:

Search for the (slowly moving) number with penalty for too high test value

You task is to design a search algorithm that will find my secret number, which is between 0 and 2^64. If your test value is too low you can test again in 1 second. If your test value is too high you are not allowed to test again the next 300 seconds.
Every second I will add 1 to or subtract 1 from the number. I will not tell you what I have done, and while it may be random it also might not be random.
How can you find the approximate number fast?
The obvious answer is to use a binary search, but since the penalty is high for guessing too high, I would think it needs some adjustment.
Background
I need to find the speed of a system. The speed changes slowly. It takes 1 second to do a guess. If my guess is too low: no problem. If it is too high, then system reboots, causing a 5 minute delay.
My goal is to get a decent estimate of the speed relatively fast.

A:

I did some empirical simulation of a simplified version of this system. It seems intuitive that one could use a binary search, modified with a weight factor to bias the "midpoint" selection toward lower numbers. Another answer proposed 300 (so choosing a midpoint that is 1/300 of the way from the left to the right), but I wanted to check this.
I wrote a simulation (code here) which runs 1000 trials for each weighting factor between 2 (standard binary search taking the midpoint at 1/2) and 499 (taking the midpoint at 1/499). The results can be seen in this spreadsheet, and the resulting graph looks something like this:

What this appears to show is that a standard binary search does perform badly, as expected. However, the optimal weight factor appears to be something around 70 (so choosing the midpoint for the binary search as 1/70 of the way from the left to the right bound). (I'm not sure why this is true, perhaps a question for https://math.stackexchange.com.)
I did not attempt to model the target "wandering" behaviour in your question. You may modify the simulation to add this feature.

