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.