In order to make your deleted items sync when you delete them from your phone, you need to go into Messages > Options > Email reconciliation. Select the delete option and change the setting from hand held, to hand held & mailbox. Save the setting and you're set. If the setting is already set at hand held & mailbox, then change it to hand held, save the setting, then change it back and save the setting again.