What the big sites can do is add a delay when receiving from a plaintext relay, in a manner similar to greylisting and tarpiting that are widely deployed. The mail is not rejected, just delayed. The delay can be proportional to the amount of mail sent by a domain, and set to increase in time. The same can be done for outgoing mail to domains that don't advertise STARTTLS, drop the connection and retry later.
In the first phase, just issue a warning then drop the first submission attempt, to fillup the logs with a clear message that STARTTLS is strongly preferred. Gradually increase the delay so that large sites have trouble emptying their queue, and continue to increase the delay until the last holdouts can be simply shut out.
The advantage with this approach is that the user of Gmail, Yahoo etc. does not see a problem with his account, while the smaller sites and users will have delays when sending mail and receiving mail and be forced to take action.