One of your solutions was to decrease the frequency that the devices check mail. Does this actually fix anything, or does it simply decrease the number of times the window pops up?
It won't fix anything, but it will decrease the occurrences, but not just because you're checking less often.
Let me explain… assume that when a client (either Mail.app, your iPhone, or anything else) logs into the mail server it takes, say, 10 seconds to check the mailbox for new mail and log off (longer if there's new mail to download).
Now let's say you have your iPhone and Mail.app set to check once per minute then there's a 30% chance that the mailbox will be locked when either client tries to log in (for each minute the mailbox is locked for 10 seconds by Mail.app, and 10 seconds by the iPhone).
Now if the clients were set to check every 5 minutes the lockup period drops to 20 seconds every 5 minutes, or about a 6% chance.
so it may be obvious to others, but what do you mean by "switch to using IMAP, which is more tolerant"? How do I switch? What is IMAP?
There are two common protocols for mail clients. POP (Post Office Protocol) is the original, and probably more widely used than IMAP (Internet Message Access Protocol).
The main difference is that with POP the client logs in, checks for new messages then downloads the entire message. The client also keeps track of the last message ID it has seen, so it can use that to detect new mail next time it logs in
IMAP, on the other hand, just downloads the message headers rather than the entire message, and leaves the message on the server. This makes the initial mail check much faster (less data to download) and is easier to keep multiple clients (Mail.app, iPhone, etc.) in sync.
As for how to switch, it's not easy to just switch from POP to IMAP. In Mail.app you need to create a new account (Mail -> Preferences) with IMAP.
I guess I was hoping that there might be a different e-mail program I could use?
If I'm right then another mail client isn't going to help. All you're going to do is move the problem from Mail.app to whatever other app you try.