When are Bayesian methods "clearly worse" than frequentist methods, apart from computationally?
Say we have data X, and some non-finite dimensional index into the family of functions that describe the the data, called \theta.
The Bayesian perspective classically holds \theta constant and optimizes the expected loss, conditioned on the data X. The frequentist perspective, on the other hand, classically optimizes \theta, that is, it picks the best \theta over the data X, unconditionally.
This has two impacts. First, all things equal frequentist statistics will tend to be more stable, and more calibrated, but less coherent. It is commonly said that frequentist statistics will "isolate" one from poor decision making, and all things equal, that will be true.
Specific, clear wins for frequentists are bootstrapping procedures (e.g., Efron's bootstrap, the b of n bootstrap, Jordan's own scalable "bag of bootstraps" from NIPS 2011), which are methods for building what are called "quantifiers" for "estimators". In short, this means that if you have some estimator (e.g., a classifier, or a mean, or whatever), you want to be able to quantify the certainty of your estimator -- so if you've only seen 5 examples, you want to express that you're less certain about this. This is clearly a frequentist application, not a Bayesian application, and in general, it points to the fact that pure frequentist tools not only have a place in inference, but they fill a niche that Bayesian tools necessarily will not, and in some cases, cannot, fill.
The harder question is whether there are any decisions you'd prefer to make using a non-Bayesian procedure. That's basically a tautology in the other direction though.
The key here is that Bayesian and frequentist procedures provide different sorts of guarantees. Frequentists optimize for \theta, the possible set of things that could describe all of the data X, while Bayesians will assume a single describing function \theta (this might come from an "expert") and simply optimize the expectation conditioned on the data. Neither is "wrong" but in the case of the bootstrap, the result is calibrated in a way that Bayesian inference simply never will be (if it were, it would be frequentist).
EDIT: As per your second question, actually I think it's not more interesting. A classifier is a type of estimator, so all of the general frequentist guarantees actually still apply to decisionmaking.
I don't see how you can sensibly approach this kind of problem in a Bayesian way. From a frequentist perspective you're sort of spoiled for choice about how to approach this problem.
One aspect of frequentist techniques that perhaps others haven't emphasised so much, is that they tend to give guarantees about expected behaviour which hold uniformly over all possible values of the unknown parameters.
Whereas the Bayesian approach, the guarantees you obtain will only hold in an 'averaged-out' sense over the prior distribution you specify.
If you're a bit paranoid and you want a probabilistic bound on what might happen in the worst case, you might sometimes find the former a little more comforting than the latter.
In particular if you don't have much data, the influence of the choice of prior will be bigger and so the distinction will matter more.
Hope that helps, and that any stats PhDs will correct me if I've over-simplified things here.
Bayesian methods rely on the concept of "priors". A prior is a known probability about a fact, or event, or whatever it is you are modeling. Priors "seed" the network.
Bayesian networks generally need fewer samples of data to make predictions, and as a result the downside is the sensitivity of the data (aka priors) increases. Whereas frequentist approaches rely on much larger data sets that can handle noise, more effectively.
Think about GMail's spam filter for example (A Bayesian approach), if you train HAM as SPAM, that is going to have devastating effect on the efficacy of your filtering.
Thus practically speaking, if you have tons of data and looking for a signal, use frequentist. If you're building, for example, an expert diagnostic engine (think Sherlock Holmes), requiring few pieces of information to make a prediction, consider using Bayesian.
I'm over-simplifying of course, but that seems to be the gist of it.
Furthermore, who said adding more data is not allowed? Of course it is, and I agree fully, but do struggle to see how that contradicts what was said.
Think about a Bayesian spam filter, you keep training it with more "priors", over time and it gets better.