Seems to be a mix of issues. First up, services were misbehaving on BES, the dispatcher kept failing. Several reboots later, and issue for User 2 is fixed.
User 1 slightly more complex, it was the user from an earlier thread OTAFM (user name):folder info is not found (Entry not found in index 0x0404)
There was a general corruption with the folder structure in his mailfile. He had several "inbox" folders, which could not be deleted or moved. Several fixups later, those dodgy folders had gone. The change was not passing through to the state DB (or at least not quickly enough, this is the user who gave me very little time to fix. Thus the delete of account from BES, re-added to server and activated. He's currently on the plane, so will text his EA details over and get him to restart it when he lands.