Sorry if this is a bit long: I've been trying to figure out precisely what it is that bothers me about the monad "pattern" as it shows up in Haskell, and I've mostly put my finger on it. It's mainly the use of the State monad that smells to me, by the way, some of the others are quite powerful and merely indicate flexibility - note that when I said "necessary pervasiveness" is a problem, it's "necessary" that bothers me, not "pervasiveness".
Some patterns, even if they show up all over the place, are not alarming at all, because they are there to facilitate good design no matter what paradigm you work in - I think of these as "style patterns", because they're usually not enforced, and sometimes you're tempted to break from them, but without a real good reason you should usually resist the urge. MVC is a perfect example - it's not there to enable you to do something, it's there to restrict what you do so that you write better, more maintainable code. This, to me, is the signature of a good design pattern: it tells you what not to do, and it lays out a way to avoid doing it.
But others are "power patterns", if we're being charitable, and "power" is not a good word in this context. Things like the adapter, decorator, iterator, and strategy patterns (not an exhaustive list, of course) are mostly around to enable behaviors and flexibilities that the language (Java or C++, usually) makes very inconvenient. Not that the patterns necessarily make them easy, but they do make them possible, usually with the minimum friction that the language will allow - if you have to use Java, you have to know and use these patterns, because otherwise you're going to end up reinventing them anyways to get your work done.
Sometimes I think of these sorts of patterns as "patterns of delusion" rather than "power patterns." By which I mean, they spring from the fact that the systems we're trying to model don't map very well onto the models that the language at hand imposes (the "delusion"), and we end up having to shoehorn concepts into each other to make them fit. This is always uncomfortable, and when we find ourselves doing it, it's a language smell.
In the case of Java, the core delusion is obvious: everything is a noun with properties (which may be other nouns) and abilities (which may not). In order to work with abilities (verbs), we have to "noun" them first, but before they can do anything we need to re-verb them, and God forbid we want to work with verbs that act on verbs...
...thus we end up with several patterns pretty much exclusively devoted to working around the inconveniences of treating verbs as nouns. Some of the other power patterns in Java are caused by other delusions (maybe I should be less critical and say "overly specific model assumptions"? Bah, screw it...), but this is the most consistently painful.
Pure functional programming's core delusion is pretty clear as well: all state is immutable. Trivially, state is not immutable in many problems (at least under the natural description of the problem), and whenever we thread state or use state monads we're employing a power pattern to work around a restriction imposed by our language/paradigm.
Now, context can determine whether a pattern is employed for power or style: I'm fine (thrilled, even) with threading state or using state monads when they are employed as style patterns - if you're working in Scala, Clojure, Lisp, etc., and you have a chunk of code that you've decided really needs to be purely functional for whatever reason, awesome. The pattern is a restriction, not an enabler, and that makes it good. I can't offer any argument against benefits of state-free programming, I fully agree that it is incredibly useful and can make life easier, to the point that it should probably be the default in any language.
But far too often I see Haskell code where state-simulation is done solely because the problem under consideration is naturally expressed with mutable state, and the only benefits that accrue by wedging the mutable state into an immutable framework are that you can write the program at all, usually at a healthy loss to clarity. Every time I see this, it's like seeing bits of Java code written in functional style: it's ugly, it's inconvenient, and you've lost most of the benefits of the paradigm that you're mocking.
I've yet to be convinced that Haskell actually gains very much from its stateless-ness; I understand that in principle there are nice optimizations that it can enable, and parallelization becomes rather simple, but I'm not seeing it beat the pants off of impure functional languages in speed or clarity. More than anything, I think what Haskell has going for it is all the other nice syntax and power that it has (a lot of which has been mimicked in other languages because it's so nice), and I'm not sure I believe that any of that would be degraded one bit if "normal" stateful programming was added in as an option.
Agree or disagree (either way is fine, I realize there are arguments in the other direction), I think that's at least a better explanation of what I was complaining about before. I realize I'm stepping into holy war territory here, maybe I should have just kept my mouth shut. :)