Using pop3 on the iPhone, all folders are local to the phone. If you sync with iTunes, it will sync that data back to your computer. The sync has nothing to do with pop3 itself.

Hmm, it does seem that iTunes doesn't actually sync messages, only account settings.

Presumably this is also possible when using an imap account as the default behavior after setting the account seems to be to use local iPhone folders for SENT, DRAFTS and TRASH. However, in practice I'm getting that error when deleting and I don't see any local sent mail folder, so I don't see any sent mail at all.

In the Mail Settings you can change the locations of those folders to reside on the server. I've done this and now deleting mail no longer produces an error, with the deleted message being moved to the server's Trash folder. I haven't yet sent another message, but presumably new messages will be stored on in the server's Sent Mail folder.

With a setup like this, I don't believe I'll be able to sync the message content using iTunes and instead i'd have to set my desktop client to use imap. I haven't yet found any advantages to using imap on a desktop client, only disadvantages. Likely because of the way with some accounts I tend to leave mail in the account's "inbox" - if I practiced inbox-zero with every account (keeping up and dealing with mail sitting in the inbox) I suppose I could keep all my mail locally.

I'll only be using the iPhone for my main/personal email account and not the general business or customer support accounts since those generate way too much email - which I'm also not likely to reply to while mobile. I'd like to keep a decent amount of mail at my finger tips but I realize that I can't very well access the same archive I keep locally on my Mac. That would get to be very problematic with imap due to the sheer number of messages.