Hi,
If i am getting your query right, you are not seeing the items deleted from the desktop when deleted from the handheld?
Can you kindly check the link below link which points out to reconciliation of messages b/w the messaging server and the device.
BlackBerry Search Results
Thanks.