Apologies for the anonymous (and, in hindsight, mildly longish) question.

I have an etiquette question on publishing an improvement of another author's work, but I figured a thread on the matter to address generalities might be nice to have as well.

Another paper in my field reports to have solved an open problem by finding a necessary and sufficient condition for deciding if an object $X$ has property $P$. As it turns out, there are cases in which this theorem reduces to a tautology, and not in the good "every theorem is a tautology" way -- it reduces to the statement $X$ has property $P$ if and only if it has property $P$. This happens frequently enough that it seems at the very least a little disingenuous to have called it a necessary and sufficient condition.

In writing up a stronger version of the result, I have to decide how to address the previous work, leading to some fairly general questions about publishing etiquette to which the MO audience at large might have some insightful responses:

1) Usually when improving on someone's work, there are a variety of diplomatic words to use -- "We generalize soandso's work" being a standard one, providing both a nod to their efforts while also emphasizing your improvement. Or, if a result is plain wrong, no amount of diplomacy will salvage their result (though could possibly soften the blow), so you can just provide the counter-example and move on. In my specific example, it feels a little harder to address -- their result isn't incorrect, just not as complete as they seem to take credit for. I know I've had both colleagues who positively light up with joy at the thought of besting someone else's paper, and those who I think would likely contact the original author to give them a chance to contribute to the discussion in the paper. Ignoring it altogether doesn't seem like an option given that they imply that the problem is now closed. Let's take the point of view that I am a recent graduate and thus the prestige of improving a published result presumably conveys a non-trivial benefit to me -- any heuristics on how to make decisions of this form?

2) On a logistical level, their techniques are completely different from ours. What's the extent to which we should re-introduce all of their (particularly burdensome, in my opinion) notation and terminology in order to prove that our result is an objective improvement? It's a fairly simple matter to give an example which our result provides an answer to that theirs does not, but it's rather technical (maybe longer than the proof of the result itself) to show that our result handles every case that theirs does (non-tautologically). In addition to the extra clutter in the paper, the prolonged emphasis on provably improving their work seems to work against the diplomacy hoped for in the previous question.