Your mail is usually 'stored' in one of several different locations. Mail which you actually download to your Mac is stored there, but if you use an IMAP e-mail server (which you probably do nowadays) then the mail is actually stored on that server. Each of these locations has its own trash can, because this is how e-mail servers know to delete it from there.
In general, you should delete each e-mail using the trash can in the same place where the e-mail comes from. If you see a message when your e-mail address is highlighted and you want to delete that message, use the trash can in your e-mail address. If you see an e-mail when "On my Mac" is highlighted and you want to delete that message, use the trash can "On my Mac".