I didn't even know I had a deleted folder until I read your post, mine was full too and I could also find no easy way to delete. I have resorted to deleting all the data from my email account and setting it up again which is a kind of cumbersome way to do it but far quicker than ticking boxes. I don't keep any emails on my phone of any importance so it was an ok solution to me but if you have stuff on there that you need to keep then it isn't going to be a solution for you.
If you are interested then go to Settings>Applications>Manage Applications and tap All then scroll down to Email and open then select Clear Data.
If you go this route, it may be worth looking at something like K-9 or Maildroid as alternative email apps, both are free on the market. They give you lots more options and if you are going to set up your account again it's worth a try!
