Of course this is not made easier by the fact that it's a peculiar and rather improbable sentence, which makes it difficult to think of convincing scenarios.

Like the others who have replied, I don't see that the choice of tense bears any relation to whether a positive or negative response is expected.

But I don't agree that "When did I..." is the normal question in standard English (though this may well be so in American English). As I see it, the normal practice regarding the use of simple past or present perfect (in BE) applies here.

Simple past:

A: (Laughs.) I was just remembering that story you told me about John's cat.

B: Really? When did I tell you about his cat?

-- This refers to a specific occasion in the past. In a different scenario it could be several occasions.

Perfect -- referring to any time up to the present:

A: Your cat is completely spoiled and overfed -- just like your friend John's cat.

B (surprised that A knows anything about John's cat): Why (Wieso), when have I told you about his cat?

Or captain flint's example:

"You're always telling me about his cat. I get fed up of it."

"When have I [ever] told you about his cat?"

I don't see anything non-standard about that.

With regard to the other example in #1, I think that the statement "Sometimes he even left ..." will naturally be followed by "When did he do that, then?" 

Wenn ich überrascht bin, dass ich etwas irgendwann erzählt haben soll, dann erwarte ich doch in gewisser Weise eine negative Antwort

But the OP was suggesting that that only applies to a question that is in the present perfect -- or, to put it the other way round, that if a negative reply is expected then the present perfect has to be used. As I see it, that is not the case.

#4: Wenn ich überrascht bin, dass ich etwas irgendwann erzählt haben soll, dann erwarte ich doch in gewisser Weise eine negative Antwort 

I don't agree with that. In some cases I might expect what you describe; in other cases, I might expect an argument!

Anyway, I don't think the present perfect form means I expect a certain kind of answer; I think it expresses a challenge or, as captain flint said, a protest, or even just confusion. It may well be answered with a list of occasions on which the thing in question was said. Or "I don't know exactly when, but I know you've told me several times." Or any of a number of other kinds of answer.

#5: if a negative reply is expected then the present perfect has to be used.

I'd understood the OP to say that if a negative reply were expected, then the present perfect would be OK, not required.But maybe I misunderstood.

I'd understood the OP to say that if a negative reply were expected, then the present perfect would be OK, not required.

You're right, I shouldn't have said "has to".

But you suggest that (in the sort of context we're talking about) the present perfect form ... expresses a challenge or, as captain flint said, a protest, or even just confusion.

But the same is just as true of the past simple.

The OP's question was about tenses, and in my view the expression of surprise, and of any challenge/protest/confusion, is not directly connected with the choice of tense.

#7 But the same is just as true of the past simple.

You're right. Thanks for pointing that out. Either form might be used in that case.

But I think if there were no challenge/protest or confusion – if it's a straightforward question in that I know I told you about x but I don't recall when, then I think I would not use the present perfect.

Maybe that helps answer the OP's question, "So how to choose?"

I don't think it's a matter of what kind of answer is expected, but more one of what the person posing the question wishes to express: Is it a plain request for information? Then simple past. Is it an expression of challenge/protest or confusion? Then either tense. (I'm not saying this is a rule; I'm just proposing it as a possible explanation.)

Q: "When did Peter tell you about his cat?"

= "Either you or I believe that Peter told you about his cat at some specific time. Please tell or remind me when that specific occasion in the past was."

Q: "When has Peter (ever) told you about his cat?"

= I find it incredible that Peter might have told you about his cat at any time in the past - Please tell me any time in the past that proves it."

Either question can be answered "negatively" as you put it:

I can't remember/don't know [the specific time]

I can't remember/don't know [any time]

He didn't [tell me at a specific time]

He hasn't [told me at any time]