|Problems? Is your data what you think it is?|
In your list of uses of big O I think you left out one of the most common uses: a thumb-in-the-air order of magnitude. The idea is to put problems in the right ballpark, not to "prove" a particular level of complexity.
In practical coding situations, sometimes all we need is a ball park. In fact, precision can sometimes even confuse the issue. Take, for example, the post you dislike so much. I don't know that it really matters to that discussion whether something is O(log N), O(N) or even O(N!). What does matter is that a preferred test for emptiness happen in constant time rather than scale with the size of the data structure. A brief statement like "O(1) vs. O(N)" gets that point across much more clearly than a precise statement loaded with if, ands, and buts.
For the most part, the monks I see using big O do in fact know what it means and are aware of all or most of the issues involved in it. However, figuring out how to apply the theory to a particular problem is the challenge.
For example, constant factors can make the f(N) component of an algorithm essentially irrelevant. Variance and competition over system resources can make singleton runs of benchmarks very misleading. Both of those turned out to be issues in the thread you did not want to mention, and I think we all learned something from that concrete example. In fact, I think we learned more that way than we would have from a theoretical discussion.
Often times, when faced with a complex problem, posters will immediately leap to the conclusion that the problem is NP complete. Often this has to do with the failure to understand the mathematical logic of the problem. A notable example is magic squares where many posters tried a brute force solution over all possible 3x3 squares. Using simple algebra developed during the course of the thread it soon became clear that the problem actually required examination of a much smaller problem space. The mathematics needed to come up with an efficient algorithm for that problem was particular to the problem.
Those are but two examples, but I could point to many more. In general, I think it is more constructive to discuss matters like complexity in the context of a specific threads and specific problems.
As for being afraid that people would take your criticisms personally? I think that is only going to happen if you jump to conclusions about their general level of knowledge based on the way they handle a specific problem. No one likes to have generalizations made from specific mistakes. It isn't fair. People make mistakes. They overlook things. They speak in generalizations (or too much detail) when they shouldn't.
On the other hand, Monks who get insulted by challenges to their problem solving approach usually get dinged - they either grow up or go away. The regulars have been challenged more times than they can count - they aren't going to go up in flames because of yet another one.
The monkly way is to criticize a particular approach to a problem, rather than the person or their general knowledge. If you think there are theoretical concepts that may be misapplied or misunderstood, then feel free to discuss the concepts as they apply to the problem or provide links to general purpose treatments.
If you do think there is an overall weakness, a mediation might be a good choice, but I think it is probably better to do your homework first rather than just point out a problem and say "let's discuss". In my company whenever someone does that we say: mind your QRS - Query, Research, Suggest.