Oneupsmanship and Publishing Etiquette 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.
 A: I largely agree with Igor Pak's response, and I think he has the right perspective on the matter.
Two comments: [X is the author of the first paper, Y is the OP!] 
1) I'm not sure it's critical to show that your result completely subsumes the result of X if that verification is going to, say, double the length of your paper and require you to introduce a lot of terminology and notation that is far away from your approach to the problem.  It is not clear what value you are adding to the community by doing this: is your proof going to be any more pleasant to read or insightful than X's?
On the other hand, I find it slightly odd that it should be as hard or harder to demonstrate that your results imply X's than it is to prove your (in fact more general) result.  I'm having trouble thinking of an example of this phenomenon from my own experience.  Is it possible that there's more insight to gained here, and perhaps a(n obvious!) common generalization of your two approaches?  
2) A good rule about describing your own work -- borrowed from the creative writing community -- is: show, don't tell.  Specifically, you should seek to minimize the number of times in which you tell the reader how she should feel about your work.  Rather, you want to present the mathematical information which brings the reader to this conclusion.  In this case, I would recommend putting a lot of effort into the writing of the example(s) of the novelty of your approach.  The more clear and detailed your writing is, the smaller your sales pitch needs to be.  Some direct comparison may be necessary, but if you stick to comparing one mathematical statement to another, then "stronger than" has an objective meaning.  It seems that there is little in such a practice that could reasonably cause offense.
Unfortunately 1) and 2) are somewhat at cross-purposes to each other.  Regarding 1), in lieu of writing out all the gory details it is tempting to write something like "It can be shown that in every case where X's theorem applies, so does mine".  If this takes pages and pages to show, then the author might well not see / believe it at first, and it could be annoying to have to work for hours to verify someone's claim that they have trumped you.
Maybe the best solution -- although not the easiest -- is for you to carefully write up the implication that your result implies X's result in a separate document, which you submit along with the paper itself and post a copy on your webpage.  This also places some of the judgment of whether this gory extra part should be included in the paper in the hands of the referee and the editor, which is perhaps as it should be.
A: I am not sure I see what exactly is the ethical issue.  You need to be very honest and very clear - you are writing a paper not for yourself but for other people to read and understand, so that should be your first priority.  Write something like this.  "We prove property P.  This result is strongly related to the result in [..] which proves property P' and extends it in the following sense ... Let us note that in all cases our property P is at least as strong as P' (see Thm~?), while in some special cases our property P favorably compares to property P'.  Below we give some examples which emphasize the connection."  
If the matter is easy - work out carefully some examples right in the introduction.  If this is more delicate as it seems to be the case, make a new section where you can work out several examples so the reader can see that P' is saying in some cases P' implies P', while your P is saying something stronger.  If you stick to math, no one I can think of will get upset over this, and there is no need to make short broad characterizations in the introduction which might upset somebody.  At the same time you "besting somebody" will come across in exactly the way you desire.  The only downside of this approach I can see is that the paper might get a little longer due to this examples section.  But so what - the reader will appreciate the clarity, and an extra couple of pages cannot possibly affect the publication chances.  
A: It's hard to judge without details, but this is perhaps a question of metatheory. (This is what item 2 sounds like to me, but this is just an impression.)
It is not a requirement in mathematical papers to carefully explain aspects of the metatheory, but it is not prohibited to do so. In your case, it seems that their result is trivial in your metatheory while yours isn't. By clarifying your metatheory, you can carefully explain that in your paper. In many cases, you really don't need to say much about their result since the issue is likely to be with their assumptions or methodology, not with their conclusions. Such a critique should sound much tamer than an attack on their result.
Clarifying your metatheory will also separate your result from theirs in other ways. It is possible that their metatheory (presumably not carefully explained in their paper) does not see their result as trivial. Maybe it even sees your result as trivial! A reader that shares their point of view and not yours will immediately see the difference when reading your paper and will be able to appropriately interpret your work regardless of their personal stance. This could avoid further confusion of the same kind.
PS: Being a logician, I prefer the term "metatheory" for what many other mathematicians would call "context,"  "framework," "perspective," "methodology," or whatever. Don't read too much technicality into the term, the metatheory is always informal. (Only logicians occasionally need to make the metatheory formal in order to formally prove metatheorems.) If this is indeed the kind of scenario you're looking at, it should be relatively clear to you exactly what and how much you need to clarify about your own metatheory.
A: Igor Pak gave good advice on what to write in your paper. Additionally, I would advise you to contact the author of the original paper and tell them about your work before it is published. This can be a good opportunity to get to know someone who shares common interests with you and it opens possibility for future joint work. I'll bet if you talk to the other author the two of you together are going to have a new idea which is even better than his or yours alone.
And another thing. If you write to the author and start talking to him, you will have a chance to find out about the background of his work and you won't have to imagine useless things (such as "this other guy is so stupid"). Perhaps he knows that his theorem sometimes reduces to a tautology and will readily agree with you. Perhaps he thinks it only happens occasionally and will be grateful to you for explaining that this is not so. In any case, just talk to the other guy.
A: See if the other author wants to be a co-author. This is playing nice, and also, it eliminates the chance that they will be a referee.
A: This suggestion may only work in certain situations, but is it possible to split your paper into two?  One could be for your new results in the most elegant form, and the other could be primarily for comparing your results to the previous work.  You can sent the former to a good journal and throw the latter in a lesser journal or just post on the arXiv.
