After all messages were deleted in mailbox (flagged '\Deleted' by IMAP and then expunged). After that each folder was checked to be 0 messages size.

Though, target mailbox was found on disk in /opt/zimbra/store and all deleted messages were found there. Furthermore those messages are not hardlinks as they are when multiple local recipients get a single message:
Code:
zimbra@ms:~/store/0/29/msg/10> LC_ALL=en_US.UTF-8 stat 41628-37386.msg 
  File: `41628-37386.msg'
  Size: 2543            Blocks: 8          IO Block: 4096   regular file
Device: 803h/2051d      Inode: 2843035     Links: 1
Access: (0640/-rw-r-----)  Uid: ( 1001/  zimbra)   Gid: ( 1000/  zimbra)
Access: 2011-04-20 16:33:26.000000000 +0400
Modify: 2011-04-19 16:13:18.000000000 +0400
Change: 2011-04-19 16:13:18.000000000 +0400
Is there any way to clear ZimbraStore from actually deleted messages?