iPhone 4 Mail Usage Size Problem
Did you restart the phone after you deleted the emails? If that doesn't work, try removing that particular email account, rebooting the phone and then re-adding it via
Settings App > Mail, Contacts &amp; Calendar