Couple questions:
What syncing technology are you using? Push or pull?
Pull will update every x minutes or manually, depending on your setting. This is normal for POP.
Push is exclusive (pretty much) to IMAP technology. It "pushes" the mail to all devices. For this to really work, though, it will need to be set to "As I receive [mail]." You can still set to pull even with IMAP to save battery.
If you have it set to sync at x minutes, it will sync in that amount of time. If you have it set to manual, you'll need to sync for the deletion to occur. If you have it set to "As I receive [mail]" it should be automatically.