The Haskell wikibook asserts that
Instances of MonadPlus are required to fulfill several rules, just as instances of Monad are required to fulfill the three monad laws. ... The most essential are that mzero and mplus form a monoid.
A consequence of which is that mplus must be associative. The Haskell wiki agrees.
However, Oleg, in one of his many backtracking search implementations, writes that
-- Generally speaking, mplus is not associative. It better not be,
-- since associative and non-commutative mplus makes the search
-- strategy incomplete.
Is it kosher to define a non-associative mplus? The first two links pretty clearly suggest you don't have a real MonadPlus instance if mplus isn't associative. But if Oleg does it ... (On the other hand, in that file he's just defining a function called mplus, and doesn't claim that that mplus is the mplus of MonadPlus. He chose a pretty confusing name, if that's the right interpretation.)
The two laws that everybody agrees that MonadPlus should obey are the identity and associativity laws (a.k.a. the monoid laws):
mplus mempty a = a
mplus a mempty = a
mplus (mplus a b) c = mplus a (mplus b c)
I always assume they hold in all MonadPlus instances that I use and consider instances that violate those laws to be "broken", whether or not they were written by Oleg.
Oleg is right that associativity does not play nicely with breadth-first search, but that just means that MonadPlus is not the abstraction he is looking for.
To answer the point you made in a comment, I would always consider that rewrite rule of yours sound.