Whenever I'm in an interview and this question comes up I have similar issues as you. Even though I can think of certain particular problems that were a pain in the ass
for me, a lot of the times someone came and solved it much faster and in a more clever way than I did.
However it just occurred to me that maybe the hardest problem I've had was actually making up an architecture from scratch as the problem was unfolding itself, and then having to maintain it and even bring others aboard. Meaning I had to document as much as I could (even though I had very little time for this) and I also had to sometimes give more priority to a not-so-important bug (vs a very pressing issue for me), not because it was critical to any feature but because it was making it very painful and hard for a teammate to implement one which in turn would later delay some other feature.
And the major reason why there was no actual planning to avoid this as much as possible, was because features were being decided on the go by the top brass on a case by case basis, completely opposite of the original direction I was told we were going to go (which was the information I used to lay down the foundations of the project). I.e. I was told at first that this was going to be just a wrapper script and it ended up being a whole orchestrator including multi-node operations needing result consolidation, a state machine to track down the... uhmm...state of the system, and things like that.
So my point is that probably there are several axes of "hardness" in a problem that can be mixed together, and that makes it difficult to compare a problem to another (i.e. over which combination of axes are you comparing one to another?). I guess part of the response to such a question in an interview would be then to explain the context so that it can be more easily understood why was that problem perceived as hard and over which axes. Was it because the problem was an optimization one and the previous code was impossible to work with? was it because the business constrains (as I believe was my case) where surreal? was it because the teammates made it really hard to move forward (e.g. bureaucracy, defensive/aggressive coworkers, etc)?
And I know we are talking about "technical problems" but I find it increasingly hard (as my career advances) to make a distinction between what is and what is not a technical problem. If the business constrains dictate certain sub-optimal solution must be developed, and that in turn causes technical issues, was that a technical problem? if a teammate is disruptive and introduces sub-par code that later causes bugs that need to be immediately addressed now, was that a technical problem?
In my mind they probably all are to some degree just by virtue of in the end influencing whatever technical decisions are being made. So maybe that could be part of the answer? asking about what specific sense are you referring to when you (the interviewer) ask me about the hardest technical problem.