Make sure you have the options set right. Go into your messages > options and make sure that you have it set to Mailbox and Handheld or Prompt. Sounds like you are just deleting them from your BB and not the server.
Thanks for the help. I checked the settings and it is currently set to 'Mailbox and Handheld'. If anyone can send additional help that would be greatly appreciated!