It sounds like you have the answer. As long as the SMTP library you are using does the right thing when throwing the exception, try ssl first, then fallback to non-ssl, and handle that error case (i.e. total failure) if it happens.
I think you are concerned because you don't know what's going on under the covers when the exception is thrown, and if that's so, I feel the same. I don't know if your .net toolkit provides the facilities, but you should be able to make the connection with a lower-level type connection object which allows you to test whether or not it's possible to make an ssl connection and check the return value of your attempt, then decide how to proceed based on that.
It may be more trouble than it's worth though, because you might then need to bolt on SMTP functionality to your new connection type, if your SMTP library doesn't support using an already established connection. Which is the long way around saying, you're probably doing well enough with catching the exception and trying again.
In reference to @Mitchel's answer, I'd say it's perfectly okay if it's automagic as long as the right notification is made, and of course the context is right. SMTP is still pretty often plain text, so any expectation of encryption for email is pretty low. Login credentials are another matter. If this is an app an end user would use, you certainly ought to make sure they're connecting over SSL if credentials will be exchanged.