Happens to me all the time. I have the same setup.
FIRST, be sure that the messages have actually been deleted, that is, moved to the deleted items. If you move them to another folder, that won't count and you will have to delete them out of the BB manually. Then click "Reconcile Now" and the BB will update. The handheld should be on version 4 as well.