I don't know about the specific devices you mention, but the general solution is: use IMAP, not POP. Unfortunately some cellphones only seem to support POP, and many mailservers only support POP as well.

Basically, POP is a protocol to download messages from the server, whereas IMAP is a protocol to synchronize files on a server and client (specifically mail, though its architecture is a bit more generic.) Sure, you can configure POP clients to leave the message on the server, but it's not really built for that type of synchronization. IMAP has features like server-side searching and so on, letting you just grab an index (or partial index even) and have the server perform operations for you. This can speed things up immensely, especially on a slow connection, with a properly-implemented client.

For what its worth, I do have my mail synched locally via IMAP (with Mail.app), but attachments not automatically downloaded. If I need to check my mail from a remote location I can always ssh in and use pine (yeah, yeah, I should've switched to mutt years ago, I know.) I've set up OPIE (one-time password mechanism) and found a cool Java applet called VeJOTP that runs on my phone to generate the one-time passphrases, so I can just use putty if needed and log in securely from any random public machine without having my password stolen . (Worst risk would be somebody screen grabbing whatever I look at in that session. I suppose the machine could be hijacked via some other remote-access software while I'm using it though... Still, a lot better than logging into random webmail with your regular password from an unsecured machine.) I've tried regular phone IMAP clients (just on simple devices, no PDA-type phones) and not been impressed with any of them...