I tried an experiment today, and what I found out is the BB is treating the mail the same as Gmail does if accessed on the Gmail website. I usually access my email through Outlook so I never tried this until now. On the website, if you delete an email from the Inbox, it goes directly to Trash and does not go to All Mail. It will only go to All Mail if you choose to Archive it, not delete it.
So on the BB when you chose to delete the email from the Inbox on both the handheld and mailbox, it does the same thing, it sends it to Trash. The problem seems to be that the BB does not offer an Archive option. At least not yet.
On Outlook using IMAP, when you delete from the Inbox it does not delete it from All Mail, there lies the difference. What I do now from the BB is if I want it completely gone I chose delete from both mailbox and handheld. If I want it archived I choose to only delete it from device then I go into my email program on my computer and archive them. Hey, you do whatcha gotta do.