Assuming you're on BES & Exchange...
I'm not sure why it works this way, but when you delete it will take some time to delete from the Inbox depending on signal, Exchange cached mode, and the phase of the moon. Performing a reconcile now doesn't change that.
As far as the setting goes, it depends on the user. For myself, if I delete from the handheld I never want to see the message again, whereas I've found that other users delete only from their handheld, 'just to be safe'. I'd explain the different options to the users and select what's best for them.