Thank you for this helpful post! I agree it shouldn't be closed as a duplicate of the reference question if the techniques in the reference question aren't sufficient to answer the question.
However, I have a slightly different perspective about what lesson to learn from this example. I do consider asymptotic analysis of an algorithm to be on-topic, if the question is not a duplicate of our existing reference question. However, it seems to me the burden is on the poster to show their work and demonstrate that the techniques found in the reference questions don't work for their particular problem.
Bad question: "Here's my algorithm, what is its running time? I haven't tried anything / I don't know how to start." ==> will often get marked as a dup of our reference question
Good question: "Here's my algorithm, what is its running time? I've tried each of the following standard techniques and here is why each one doesn't work." ==> not a dup
It seems to me that the problem with the question you gave is that there was no evidence in the question that the poster had tried any of the standard techniques and no indication of any barrier to them working, and in the absence of that, it seems like trying the standard techniques is the obvious answer.
So, while I do see your point (and I'm glad you caught the issue with that particular question!), I'm not sure a new standard is necessary. We already ask that people should do research before asking and show us in the question what approaches they've tried and rejected and why. If people do that, I don't think this issue will arise. And in my mind this kind of question is a rare case, so I'm not convinced it is frequent enough to warrant a major change in policy. Just my sense.