Is the order of unfreezing delayed goals determined?
For instance, assume that when(nonvar(X),p) and when(nonvar(X),q) have been performed, and X now becomes bound. What is the order of executing p and q?
Similarly, what happens after when(nonvar(X),p) and when(nonvar(Y),q), when later on X and Y are bound in the same unification?
Is the behaviour similar in other (major) Prolog implementations?
As is, I think SWI-Prolog maintains the order. For the second scenario, that is true as well, where unification is performed by depth-first traversal. If the unified terms are rational trees it gets rather hard to predict.
More relevant is indeed what other systems do and what should be documented as standard in the (unlikely 
) event coroutining becomes part of the standard. My first intuition is that the order should be unspecified.
“As is, I think SWI-Prolog maintains the order.” Does this mean “first frozen – first unfrozen” ? Can we say anything about queries frozen on variables which then are bound during the same unification?
Even if the order is specified, I think it would be a mistake to depend on it. This also applies to multi-thread or multi-processing – no assumptions should be made about “fair” scheduling, for example, and keeping that in mind has helped me write more resilient code.
I think my text is fairly clear: order of when/2 calls is maintained and the order of unification is maintained. A single unification that binds multiple variables does so in depth-first tree traversal order.
But, as @peter.ludemann says, I would not rely on it. If ever there is a reason to do this differently, this may happen. The documentation claims no ordering and I do not intend to document the order, exactly for this reason.
This could only change if (1) there is a good reason to have a reliable order and (2), this is widely agreed upon by the various Prolog implementations and we decide to specify the order. I consider this unlikely, but one never knows 