Deleted messages still on server

There is a delay between the Mail.app or email client used and the server with an IMAP type account although using the Synchronize function in Mail should work. Try rebuilding the account's Inbox mailbox also.

Test when quitting and re-launching Mail or when taking the account offline and back online in Mail.

I have experienced very few if any such bugs with Mail.

The problem with the server might be caused by a cache problem or corruption. When was the last time you used a system and user cache cleaning utility?

There might be a problem with Mail's Envelope Index file which is easily targeted.

I can't import a Mail mailbox,

Any error message provided? A common mistake people make when using the Import Mailbox function is trying to choose the mailbox file or folder instead of the location that contains the mbox file or folder.

and I've seen countless reports of people with messages
disappearing, messages on an IMAP server that aren't getting
downloaded, etc.)

Messages with an IMAP type account aren't downloaded as with a POP type account. The mailbox is synchronized with the server and if you select All messages and their attachments for Keep copies of messages for offline viewing, all server stored messages are also cached locally on the hard drive but still are not downloaded.

I've had a .Mac account since before it became a paid service and I also access two additional IMAP type accounts and I've never experienced such a problem. Most of the reports I've seen here in regards to messages mysteriously disappearing from the server with an IMAP type account have nothing to do with the Mail.app. The problem usually falls on user error by creating the account as a POP type account with another email client on the same or different computer with messages being removed from the server by the email client accessing the account as a POP type account.