How about a delete button next to each message? To delete multiple messages, the user would fall back to the current interface.
Pro: Single click for a common operation. (Was: click + long move + click + drag + click.)
Con: Uses up a lot of screen real estate.
If the above takes up too much screen real estate, the drop box could be replaced with
Move selected to: [ Inbox ] [ Archive ] [ Deleted ]
Pro: Removes a click+drag, an operation requiring a fair bit of precision.
Pro: The options are not hidden in a drop box.
Con: Not forward compabtible if support for more folders is added.