It's possible that deleted messages are being moved to the deleted items folder and never purged. Check the following setting:
Unity admin > Class of Service > Messages > Deleted messages are copied to the deleted items folder
If this option is on, you'll want to use Message Store Manager or Mailbox Manager in Exchange to purge old messages.
http://www.cisco.com/en/US/products/sw/voicesw/ps2237/products_tech_note09186a00800d6824.shtml
Hope this helps.
Brandon