The "Delete on" option only applies to deleting from the handheld.
If you use shift+del to delete messages (bypassing the deleted items folder) then they will not be removed from the handheld.
You can try going into options on the handheld and turning off wireless reconcile, then turn it back on.
I have also run into a case where turning off wireless reconcile on the handheld actually turned it on. But that was a one off case.
Oh, also remember that reconciliation can take up to 20 minutes.