Mail removed from the inbox (or most other "folders" on gmail) works as expected. However, they still remain in the "All Mail" folder, which doesn't appear to be accessible to POP/IMAP clients.
When a message is marked as deleted and expunged from the last visible IMAP folder: