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.
CrackBerry is in no way Affiliated with BlackBerry. We take pride in our unbiased content, however do occasionally receive free products from vendors that we review or discuss. For more info click here.