If Tim tells the truth with probability $p$, you simply get that you should guess what he said if $p<\frac{1}{1000000}$, and $p>\frac{1}{1000000}$. For Tim the optimal choice is to have $p=\frac{1}{1000000}$ in order not to give you any information: Anything else is playing on psychology and human biases, which exist in reality but trying to play a "perfect" game by assuming your opponent is not also leaves you vulnerable to exploitability, as you mentioned.

It seems you are trying to get a deeper understanding of human fallibility rather than playing optimal games. Have I misunderstood it?

Optimality goes out the window when you throw psychology into the mix. If you know your opponent is better than you at this game, you absolutely should just randomize and take your $0 average payout (or choose not to play, if money is less than linear utility to you). If you know your opponent is foolish or really innumerate (like doesn't understand probabilities, and thinks 302 is a "big enough" number to fool you, pick 302 or 301 (depending on your best read of your opponent). Remember, the only reason to randomize, rather than picking the single number you assign highest chance to, is to prevent your opponent from adjusting, which doesn't matter in a one-shot. If this repeated or your opponent knows you before this, you could assign higher weight to 302, near 302, and very far from 302.

I used to hang with (and still am Facebook-acquaintances with many) a gambling group (mostly +ev focused - poker, some sports and horse betting, +EV video poker, rarely some blackjack (opportunities had mostly dried up by then, though we did have some ex-MIT-team members), and a bunch of fun-but-negative games). For a few years in the late 90s, I participated in $100 buy-in single-elimination roshambo tournaments, as well as settling a LOT of bar bills and other small contests by rock-scissors-paper. It became the STANDARD opening statement for the defender to accept a challenge of "shall we roshambo for it?" with "OK, I'm going Rock". The Simpsons reference "good old rock, nothing beats rock" was optional. As was ACTUALLY throwing rock, though it was much more frequent than 1/3, because winning with a declared throw came with extra bragging rights. And because we all knew this, scissors was second-most-common after declaring rock - recurse as deep as you like. The common exclamation on losing was "Damn! I was thinking TWO LEVELS (or 5 or 29 or 101 or any 3N+2) above you".

In any case, even for a stranger, you have a lot of information just from the circumstances of the game, his or her mannerisms, etc. If you think you have enough information to pick a distribution other than "equally likely for all numbers equally likely", you've got an edge. Also, for a million-to-one payout, I'd have to consider that the chance of being cheated is not insignificant either, and my edge would have to be higher than that, which is unlikely.

This is related to https://www.lesswrong.com/posts/RzvEs2fj8kFwezXNi/how-to-avoid-schelling-points [LW · GW] . The main difference being your example is adversarial - the stranger wants to trick you (probably - the chance that it's an altruist or just a bad player is in scope). But it doesn't matter - once you have an anchor, the distribution is no longer flat.

A paradox is a sign of an inconsistency.

It's pretty clear that it isn't rational for Tim to tell you his real number.

Assuming Tim is trying to win.