I wouldn't say STARTTLS is fundamentally flawed. Given a mechanism for declaring a policy of TLS being required, a middlebox downgrade attempt to deny STARTTLS should merely cause the sender to abort the SMTP transaction. This is no different from a middlebox hijacking a pure TLS tcp connection. In both cases it's on the sender to abort if a secure connection cannot be established.
A couple of years ago, someone with a .gov address told me they couldn't subscribe to a mailing list I manage, since the mail server didn't support TLS.
Adding the appropriate option in Postfix fixed the problem, and I think there were further options to require TLS.
I wouldn't consider the initial call to starttls to be insecure. It is just a matter of a few static bytes containing an SMTP HELO and the ascii bytes "STARTTLS". This can be used to establish a secure TLS connection without compromising any private information. It is only insecure if the client decides to proceed with the rest of the SMTP transaction if the server (or middlebox) nak's the STARTTLS. Which is no different from a middlebox presenting a self-signed TLS certificate. A few extra plaintext bytes at the start of the TCP connection containing the string "STARTTLS" doesn't change anything compared to a plain TLS socket. It is always up to the client to decide if it wants to proceed in the face of bad or nonexisting TLS.
