so get this... you have to check each one a single at a time, but guess what... once they are all selected, hit menu and what do you know, there is a "deselect all" genius!
Via a browser is your best bet. Go to the trash folder and there will be a "delete all trash" button above the emails. And as others have said be sure you have all your devices (and your account) as IMAP. You can do all this from the browser on your Droid if you're not near a computer.