After archiving user mail, Exchange Mailbox size not free-up

beside replies you have received, I suggest you share the archive report for that particular user(s)sometimes in the mailbox archive policy you might not selected all options (for example calendar items).

In addition, verify the dumpster/deleted items folders in the mailbox. Sometimes these are not properly managed by Exchange. Mailbox shows small, but actual size is large. Dumpster/Deleted Items is not taken in account when showing size (as far as I recall).

Also check

the shortcut type of the items in the mailbox.

Make sure you when you remove safety copies, like AmoIB described. Often times it it linked with missing backup checks.

Couple of basic checks

1. Review Mailbox Archiving Policy -> Archiving Actions -> Delete original item after archiving
2. Review Vault Store Properties -> Safety Copies -> Remove original items