Turns out this was an issue with the deleted items folder in the mailbox becoming corrupt. I found this, by right clicking on the user's deleted items folder and noticed in the location dialog that it was blank.
To fix the problem, I set up the user with an exchange profile on my system, as I have admin rights over all my users exchange mailboxes. Then I opened the users profile (mailbox), and upon opening it stated that the server and client settings were different. I set the mailbox back to server settings and it restored the deleted items folder.
Now that the deleted items folder has been restored the deleted items are actually going to the deleted items folder. This in effect is causing them to be removed from the blackberry.