This should have been obvious, but I didn't think of it right away, so others may not have either: log in (via a dialup or using the .net or .org names, e.g. panix3.panix.net) and change your login password, because the hijackers may have grabbed your password when you tried connecting early in the problem.
.
From:
no subject
key on the other side of the link, specificially in order to avoid this kind of attack (well, theoretically, to avoid man-in-the-middle attacks, but this wasn't all that dissimilar).
If you were pulling your mail over SSL, of course, this may not be sufficient -- I don't know nearly as much about how POP/SSL does host-based authentication.