That 581mb is probably the sum of all the mails you've downloaded onto your handset. You may have deleted the mail account associated with the phone, but not the actual mails themselves. Can you Clear Data for the mail app via the apps menu?

 

I know using Astro or ES File Explorer, you can search for files and folders on the SD Card which are taking up the most space, I'm not sure if they can search the actual phone memory itself unless you're rooted.

It's worth giving it a shot?

 

Same problem here - solved (for now, at least, for me...)

I had the "Low on Space" warning, and found that the mail app was using a massive 770MB!!
I deleted current mail and checked it had gone from trash also - next-to-no difference.
I deleted the email account - no difference.

After lots of searching....

Following these instructions for TEMP ROOT here:
http://androidforums.com/desire-hd-all-things-root/383322-guide-temp-root-any-dhd-gb-build-downgrade-1-32-405-6-easy-follow.html
I gained temporary root access, and tried deleting large number of files in the files in /data/data/com.htc.android.mail/ (which appeared to be the attachments of emails deleted long ago). This made a small, but still not significant difference. I searched through the file system some more but couldn't find where all this memory was being used.

What worked for me, once I had temp root, was the pm command. At the # commend line of temp root, type pm for an explanation of its usage.
I used the command:

Code (Text):

1. pm clear com.htc.android.mail

to "delete all data associated with the package"... which reduced mail's usage from 700MB+ to 64kB

(Obviously, if I hadn't already deleted it, my email account and mail would have been swept away also...)
Now... to more carefully setup my email account again...