1. Did you ever log into the SMTP server manually and after login type EHLO? It tells you a lot about how the server is configured, including what kinds of authentication it supports.

2. Divergent ports: Comcast and Cox Communications, among others, handle SMTP authentication on port 587 (as opposed to port 25). This RFC and this newer RFC explain a bit more of what is going on.

Update: added better references.