If you have imperative state then toy uses of the state monad might be overkill. But, for example, in a parser, imperative state is unlikely to help you. Here, you want state to be discarded at failure and old states restored by backtracking. The execution paths are highly complicated (as they always are when you are working with what are effectively continuations), and trying to reason about these paths in the face of imperative update isn't easy, and is likely to lead to weird bugs.
Toy examples are not generally going to help you appreciate monads, and I think there's a fourth requirement to make them work in a language: you need a powerful type-system. I'd say that monads haven't taken F# by storm because F# isn't powerful enough to type-check a library for arbitrary monads. And you want that, because when it comes to reasoning about code using such libraries and then applying it to a monad assembled from a stack of several other monads, you really want your type-checker around.
Ocaml's type-system is powerful enough for this, and I still reach for my monad library when writing Ocaml code. It's syntactically heavier than Haskell, but not too painful. The solution is to make all your monads into modules, which would be a bit like making every monad a dictionary and passing it around explicitly. This is basically what Haskell ends up doing with type-classes anyway, and what Gabriel Gonzalez has suggested one do explicitly:
http://www.haskellforall.com/2012/05/scrap-your-type-classes...
If you follow this approach, Common Lisp and any other language can pull it off by making all monads into dictionaries. All you lose is the type-checking.