Is Wireless E-Mail Reconciliation enabled on your device ? (Messages/Options/Email Reconciliation)
How are you deleting the message from the handheld? Are you deleting on Handheld & Mailbox, or Handheld Only?
If you're using 'Delete Prior', those deletions will not reconcile back to Lotus Notes.
Additionally, deletions from the Handheld can take up to 20 minutes to reconcile back to Lotus Notes.