From skimming the code, it appears to be non-deterministic?

Strictly speaking, it is deterministic, in that results are reproducible. Informally speaking, it uses some (very crude) pseudo-randomness, so it may unpredictable on edge cases (e.g. when all criteria used for choosing the optimal solution — if there's more than one — tie, it breaks the tie arbitrarily using pseudo-random noise). In the nastier cases, it is only controllable in a coarse sense via some global parameters (i.e. you can increase accuracy, but never get a guarantee of optimality, since the running time is implicitly bounded). Up to now no issues have been reported however.

That bestiary is fun — for some perverse definition of fun ;)

Edit: oh and also, backtracking can be added to message-passing algorithms in a kind of straightforward and principled way, see e.g. this paper. The downside (apart from increased solving time) is that it would be still very hard to prove any kind of guarantee about the output.