The bad idea is not the use of NTLM, but the lack of use of SSL. Without SSL, data travels unprotected, and, in particular, active attackers may hijack the connection (for instance right after the authentication was performed). No amount of NTLM will fix that.
To use SSL with STMP, there are two ways:
Run the whole SMTP transaction in a SSL server. The client must be aware, beforehand, that it is expected to begin the transaction by a SSL handshake. The traditional port for a STMP-within-SSL server is 465.
Have the client and server use
STARTTLS. Connection begins with the "normal" port (25), but the client and server then negotiate the use of SSL/TLS and, after that negotiation, begin a SSL/TLS handshake.
Either way, you must configure the client not to send the password "as cleartext". Most clients can be configured that way.
If you use SSL/TLS then sending the user name + password "as is" is fine. If you do not use SSL/TLS, then switching from basic authentication to NTLM may slow down the less competent attackers, but don't believe that it will really thwart them. The cryptography in NTLM is not exactly worth a lot of enthusiasm, but the biggest problem with raw NTLM over an unprotected socket is the same as raw login+password over an unprotected socket: the socket is unprotected.
Compared to basic authentication, NTLM does not show the password itself, so passive only attackers will not learn the password immediately; however, they obtain a password hash, with a very fast hash function (a few MD4 and MD5, at most), meaning that brute force on the passwords will be effective. A passive-only attacker with a good GPU still has a good chance of breaking some user passwords.
A good reason to switch to NTLM is integration with other authentication methods, e.g. smart cards. But if your users have passwords, then basic authentication does the trick with less hassle.