You have two mailbox trees. Each tree has nodes, which contain:

 - node name
 - GUID (optional)
 - timestamp (last renamed)

The GUID uniquely identifies an existing mailbox. If there is no GUID, the
node is a "directory", which isn't a mailbox itself but may (or may not)
have child nodes.

The objective is to create an algorithm to make the trees identical with 1)
as few operations as (reasonably) possible and 2) preserving the
name/location of the mailbox node which has a higher timestamp (and its
children, unless they have newer timestamps). The changes must be done with
a series of (atomic) operations. The algorithm must be symmetric (i.e.
algo(tree1, tree2) = algo(tree2, tree1)).

Operations that are allowed on the mailbox tree:

 - Create directory (always a new leaf node)
 - Create mailbox (either a new leaf node, or promoting an existing
   directory node by assigning it a GUID)
 - Rename node: Change node's name and/or its parent. All of the node's
   children get moved along it. The new parent cannot be the node's own child.
(- Deletions shouldn't be necessary, mailboxes are deleted before this
   algorithm and extra directories can be deleted afterwards.)

Some problems:
 - Swapping names of two mailbox nodes: Need to rename one of them to a
   temporary name.
 - Moving a mailbox node under itself: Again needs temporary rename.
 - Same mailbox name is used by different GUIDs, but both GUIDs exist in both
   trees: The one with higher timestamp keeps the name, the other is preferably
   renamed to its new name (unless it currently exists as well, in which case
   either rename that first (and avoid infinite loop) or use a temporary name).
(- Non-problem: Same mailbox name is used by different GUIDs, but at least one
   of them doesn't exist on the other side. This is handled elsewhere by
   merging the mailboxes and assigning a new GUID to the other.)
 - Moving a directory under another branch: This needs to be detected by
   looking at the child mailboxes. But the children may also have been
   moved or new children may have been created to both sides, so the detection
   needs to be somewhat fuzzy.

Update: Create mailbox operation isn't really needed either. The mailboxes
can be created after this algorithm. Also assuming the rename operation can
automatically create missing parent directories, There's no need for
anything else than the rename operator itself.