KingofMean,
I am not sure what version of software you have, but you could try right-clicking on the mailbox to see if there is an option to delete messages. If not then the only other option is to delete the mailbox and recreate or manually delete them through the phone. I think there was a way to do it through OAM if you have an EM, and it may work through a basic VM; although I am unsure of the commands to do it.
Thanks,
TE