I think it'd be more helpful that we talk about the semantics of the phrase (1) 뭘 했었을 때 that 먹었을 때 is based on, versus the phrase (2) 뭘 했던 that 먹은 is based on.
(1) 뭘 했었을 때
You're right in saying that 뭘 했었 "다" is strictly the past tense of an action, but when you conjugate it to 뭘 했었 "을 때", then it becomes the conditional premise A of the proposition if A then B. And the same conditional premise 뭘 했었을 때 is used to complete the proposition that could take place in either the past or future. So in English, the conditional premise 뭘 했었을 때 depending on its tense is equivalent to saying either when you did that OR when you do that.
i. Example of conditional premise 뭘 먹었을 때 in the past tense: 너 김치 먹었을 때 배 많이 아팠잖아. When you ate kimchi, you had a bad stomachache.
ii. Example of conditional premise 뭘 먹었을 때 in the future tense: 너 김치 먹었을 때 배 많이 아플거다. When you eat kimchi, you'll have a bad stomachache.
(1) 뭘 했던
뭘 했던 is also the conjugation of an action in the past tense, but it behaves more like an adjective to describe the subject that carried out that action.
i. Example of adjective 뭘 먹은: 밥 많이 먹은 강아지 똥 많이 싼다. The puppy that ate a lot poops a lot
Because 먹은 is an adjective, adding 때 would be redundant as 때 more or less describes the state of something. So 먹은 때 would sound unnatural to native speakers. At least to me it does.