Exchange 2013 Public Folder Move Error: Destination Folder Hierarchy Inconsistent Transient Exception

When we migrated to Exchange 2013, we only set up one Public Folder Mailbox, since our Public Folders weren't heavily used. Soon, we started getting SCOM alerts that there were too many connection attempts to the single PF Mailbox.
After creating a new PF mailbox and attempting to move some of the Public Folders over, I kept getting the following error:

Destination Folder Hierarchy Inconsistent Transient Exception has occurred

Luckily the fix was pretty simple, just restart the Mailbox Replication Service (MRS) which controls mailbox moves.

**Note** You'll need to restart the MRS on all of your servers.

That being said; I'm not sure what causes this issue, especially since we're on RU11...you'd think MS would fix this by now.