STS is built around cached policies. It does not require an HTTPS transaction per message. Since a very high fraction of all email is sent between the sponsoring organizations (Google, Yahoo, Microsoft, and the ISPs you mentioned) it is likely that the aggregate cache hit rate will be approximately 100%.