smtplib's "complex" methods, login and sendmail, try to EHLO or HELO if 
it hasn't been done yet.  login also checks to see if the EHLO response 
included the ability to do authorization.

starttls seems to me to be similar in nature: why should it not try to 
EHLO or HELO, and check that self.has_extn("starttls")?

You'll get more traction on this if you submit a patch.

I've attached a patch against 2.4.3.

The patch does the following:
- Factor out the duplication of EHLO/HELO in login() and sendmail() to a 
new function, ehlo_or_helo_if_needed().
- Use ehlo_or_helo_if_needed() in starttls()
- Check for the starttls exception in starttls() in the same way as 
login() checks for the auth extension.

From RFC 2487 section 5.2: "The client MUST discard any knowledge
obtained from the server, such as the list of SMTP service extensions,
which was not obtained from the TLS negotiation itself. The client
SHOULD send an EHLO command as the first command after a successful TLS
negotiation."

So the starttls() method should probably also be clearing helo_resp and
ehlo_resp (and maybe anything else discovered by ehlo()).

There are servers in the wild that will (a) refuse to talk to you unless
you issue another EHLO after TLS is negotiated and (b) offer a different
set of ESMTP features (such as only supporting SMTP AUTH after TLS). 
This patch isn't enough to talk to such servers.

jamesh, I attached the patch for that to the already-existing bug, filed 
in 2003: http://bugs.python.org/issue829951

Accepted and applied, with appropriate documentation updates.

In svn trunk r60020 for 2.6.