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).