Re: message delete hot key seems more reliable:

[Travis Siegel]

Another method you can use is to open the trash mail folder in the  
list of folders, select all using command-a, then hit the delete  
key.  This is the method I use all the time now, as the other method  
rarely worked for me.