A couple of different ways; You can delete and reinstall the mailbox, losing all greetings, or change the class of service to something that deletes all messages older than x days. It's cleaner to do the second, so the user only loses the "old" messages.
After the dust settles, pick a reasonable number of days to retain and modify the COS to that for that user (as in maybe 50 messages).
LkEErie