I am beginning to understand the issues here and below I have attached a
proposed fix: it adds support for legacy ssl-only smtp servers.  I have
based this patch on the version of smtpmail that can be found in
gnus/contrib.

The patch is mostly a conservative extension, except in one respect:
previously, when credentials where found in
smtpmail-starttls-credentials but gnutls-cli was not found,
smtpmail-open-stream would open a non secured connection to the smtp
server.  I think that's a bug: if the user has explicitly added an entry
in smtpmail-starttls-credentials, then clearly he expects a secured
connection: a non-secured connection should not silently be used
instead.