Sorry to bring up this zombie, but I just discovered this thread and had an idea for a simple enforcement mechanism.
The idea is to twist the secret nature of order submissions. Rather than each person submitting only their orders in secret, a player can submit a "contract" that includes obligations for any unit on the map.
- An obligation can be a move or a prohibition on a move. A prohibition on the move is either a specific move that isn't allowed, or one or more powers being prohibited from moving into a region.
- A prohibition can be for 1 or more turns (e.g., you can set up a multi-year DMZ)
- An obligation in the form of a move translates to that move actually being ordered; an obligation in the form of a prohibition translates to that move being considered illegal for the turn.
- All powers whose units are in the contract can see all of the obligations in the contract -- and what they see are the actual obligations, not just a promise.
- Once all parties to the contract agree on it, those orders are locked in and can't be changed unless everyone in the contract agrees to nullify it.
- If any party rejects the contract, then it is nullified -- I could see variants as to whether this is open ("France rejected the contract") or secret ballot.
For instance, let's say England and France are negotiating a DMZ in the channel for spring '01. Today, they just promise to keep out of it. Under a "UN" type proposal, they might both submit a contract to stay out of it -- and if one of them violates that contract, then... unknown what happens.

Under my proposal, England would suggest a contract like:
- F Lon -> Nth
- prohibit all units from France or England to move to Eng for 2 turns
In other words, England is promising that they'll move to Nth, and in return, asking for a 2-turn DMZ in Eng. If France accepts the contract, then England doesn't need to (and can't) submit a separate order for Lon; it's already ordered. France can submit any order for Bre, but "F Bre -> Eng" would be rejected as invalid (other players would see that it was rejected, but not see why -- that is, they wouldn't know which contract forbade it).
A power can agree to as many contracts as they like, so long as they don't violate each other. If a contract would be violated, the player still has to manually reject it (otherwise you could use contracts to probe for info on other contracts, to see if they were instantly rejected). So in my example above, France can separately come into a contract with Germany that includes "F Bre -> MAO," but may not agree to a contract that includes "F Bre -> Eng," since that would be in violation with the previous contract with England. In the fall, France may not enter into a contract that includes MAO -> Eng, since that would be in violation of the 2-turn prohibition of moves into Eng.
One advantage I can see with this variant is that it doesn't require the legalese that may otherwise turn some players off. It's a relatively simple game mechanic, it's automatable and deterministic, and yet it gives you that ability to sign a contract. And I could imagine more complicated obligations being added later (for instance: "at least one Italian unit must support Paris to hold" -- meaning that if Italy has two or more units bordering Paris, then at least one of them must support Paris to hold, or else all units not otherwise obligated by a treaty will be ordered to support Paris H, regardless of what Italy ordered).
------------------------------
One observation: This would really tip the balance in favor of certain countries. For instance, virtually everyone agrees that Germany and Austria should not attack each other early on... but fear of a crazy neighbor still forces them to keep a unit behind to guard against the possibility. If they agreed to a 3-turn DMZ in Tyr/Boh, their alliance gets much stronger. The Juggernaut also gets stronger, since neither country needs to worry about Bla. But then again, the Lepanto
also gets stronger, since Italy and Austria can enter a contract prohibiting either of them from entering the other's home SC.
My one worry would be that the increased stability would make the game a lot less interesting. People would quickly fall into contracts establishing common alliances, and the game would be ossified from there. But maybe not... it would definitely be something I'd be willing to try.