I'm glad to hear that others are facing this problem as well. Those of 
you who are: how are you dealing with it? Are you simply requiring your 
users to use a particular version of the compiler? Or switching on 
Sys.ocaml_version?

Quoting Jean-Christophe Filliatre <filliatr@lri.fr>:

> EEK Cooper writes:
>
>  > My team just noticed that the behavior of Map.fold changed in OCaml
>  > version 3.08.4.
>  >
>  > I'm concerned that the OCaml team would change the behavior of a
>  > library function so late in its life. I understand that it was thought
>  > to be "wrong" <http://caml.inria.fr/mantis/view.php?id=3607>, but
>  > changing the behavior of an existing function breaks existing apps and
>  > shouldn't be done lightly.
>
> I must agree  with you since we also  got a similar bug in  one of our
> apps due to this Map.fold _implementation_ change.
>
> However, we must also admit  that we were using an unspecified feature
> of the  standard library. If  I remember correctly,  the documentation
> was saying that  the traversal order was left  _unspecified_.

For the record, I don't think this is true. My copy of map.mli, as part 
of OCaml 3.08.3, says:

     val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
     (** [fold f m a] computes [(f kN dN ... (f k1 d1 a)...)],
        where [k1 ... kN] are the keys of all bindings in [m]
        (in increasing order), and [d1 ... dN] are the associated data. *)

specifying the same ordering as the current version. Also the original 
bug ticket <http://caml.inria.fr/mantis/view.php?id=3607> about the 
issue asserts that it should behave according to the documentation.

Since the behavior was NOT unspecified, it was reasonable to assume 
that the documentation suffered from a simple typo, and to expect the 
behavior not to change. I believe the documentation should have been 
fixed rather than the behavior.

Ezra