More than 18 months after Gmail is introduced, they have finally done it!
I selected quite a few mails from mailing list which I don't have time to read, and search for "Move to Trash" option in the drop down menu. Then I spotted the Delete button. Wow. I have to check that it wasn't a GreaseMonkey userscript doing the trick -- it is really a genuine Gmail delete button! I thought they'll never do it but maybe they do listen to their users this time.
Then I found it in their new features section:
When you're positive you won't need a message, use the Delete button to send it to Trash. Deleted messages and conversations are permanently removed from your Gmail account 30 days after you send them to Trash. Deleting unimportant mail is a great way to free up some of your storage, but with more than two gigabytes, you could even keep those messages, too! So, if it's possible that you'll need a message or conversation in the future, we recommend using the Archive feature.
30-day permanent deletion doesn't seem to work for me -- I always have to manually dump my trashcan. Anyone has the same issue? Well, not that I need the space, but I am really a tidy person, you see...
Update: As reported on Google's official blog: Our shipment of delete buttons finally came in.