I have had a similar problem with clients sending email to a btinternet.com domain. It wasn't until a nice network technician sent me the error logs from the BT server that I had any idea what the problem was.
It seems that the server is sending the STARTTLS command in it's preamble, however Exchange 2003 does not understand this sendmail specific command. Sendmail isn't meant to insist on this and if the peer doesn't understand should continue without it, however for some reason it's not doing this and is simply dropping the connection.
I have also found Yahoo emails not being sent and I can only assume that it is for the same or at least similar reason.
I have no idea how to resolve this STARTTLS problem though, I've read half the internet it feels like and still no luck. Anyone got any ideas?