I ran into a simular problem with Earthlink.  I have a POP e-mail
account at Earthlink.  Normally when connected via a land line, I just
open my email application (Netscape Mail 7.2), download my e-mail or
send my e-mail.

I found out when I was on the road and using my cell phone as a modem,
I could download my e-mail fine, but I couldn't send any e-mail.
Normally when I would send e-mail it would go out through the SMTP
server (smtp.earthlink.net).  To send e-mail using my cell phone as a
modem, I had to use a different server called SMTPAUTH
(smtpauth.earthlink.net).  When you use this server, you need to type
in your password before the e-mail will go out.  Earthlink does this to
prevent SPAM.  In other words, they want to verify who is sending
e-mail through their servers.

You need to check if your ISP has an authentication smtp server that
you can use.  The only other alternative is to use webmail.  However
with webmail, your sent messages are stored on their server rather than
locally on your computer (or Treo650 in your case).