Solution has been found. You need to run a mailbox clean up on the System Manager for Exchange, deleting any inactive accounts.
This will delete any multiple folders in the MBX directory. Once they are gone, you can remove the user as normal.
In this case, I had to remove the users and re-create them to fix the mailbox problem (which was showing messages, but no message were available, since there was 3 folders for one user)