Is this a POP or IMAP account? If it is IMAP then your mac and iPhone
are connected through the IMAP server. Each device sees the same identical mailboxes and messages. If it is IMAP then on your Mac try Mail > Mailboxes > Synchronize "
theaccountaddress". Another, previously hidden mailbox may appear with all the messages in it.
That happened to me once with a Gmail account. I finally had to logon to the Gmail web portal and delete the messages from the previously hidden mailbox. I solved the issue permanently by changing a Gmail setting through the web interface, but for the life of me I don't remember what setting it was