Take each of the following steps that you haven't already tried, testing after each one. Back up all data before making any changes.
Step 1
From the Mail menu bar, select
Window ▹ Connection Doctor
Double-click the problem SMTP (outgoing mail) account in the window that opens. it. Another window will open, showing a list of all the outgoing mail accounts. The one you clicked will be selected.
Select the Advanced tab in the settings for the account and check the box marked
Automatically detect and maintain account settings
if it's not already checked.
If there's more than one problem account, repeat. Close the window and save the changes.
Step 2
Open the SMTP server list again. Make a note of the settings of the problem server, then click the minus-sign button to delete it, and confirm. Click the plus-sign button and recreate the account with the same settings.
If you're using Gmail, delete the account completely in the Internet Accounts preference pane and recreate it. The "detect and maintain" option must be selected in the Advanced settings for the incoming mail account.
The messages will be resynchronized with the server automatically, which may take hours if the mailboxes are very large.
Step 3
Quit Mail if it's running. Launch the Keychain Access application and enter the name of the outgoing mail server in the search box. For example, if you use Gmail, enter
smtp.gmail.com
Make a note of the password, then delete the keychain item(s). The next time Mail connects to the server, it will prompt for the password. Enter it and save the password in the keychain.
Step 4
If you're using Gmail, log in to your account on the website and, in the account settings, click the link to "Sign-in and security". There should be a option somewhere on the page to "Allow less secure apps". Enable that option and save the change. Note: I don't use Gmail and I haven't tested this solution myself. If it doesn't work, either go to the Google user forums for help, stop trying to use Gmail with Mail, or just stop using Gmail altogether (highly recommended.)
The mail server may be using a weak, obsolete form of encryption to secure its communications with the clients. The update to OS X 10.10.4 changed the behavior of Mail and other applications so that they no longer tolerate weak security.
Log into the mail account on the website and see whether there is a security setting you can change. I can't be more specific. Refer to the service provider's documentation.
If there is no setting, persuade the server administrator to upgrade the server's security. He or she should do that anyway. Weak security affects all clients, not just Mac users.
Otherwise, you don't have any good options for continuing use Mail with the service. You could disable SSL in the advanced account settings, but that's very unsafe and may not work at all.
You might be able to get a more flexible mail client, such as "Thunderbird," to work with the service, or maybe you can access it via webmail.
Ideally you should switch to a better mail service provider. You wouldn't have this problem with a well-run service. The risks of weak SSL have been known for a long time, and competent server administrators have already taken the simple steps needed to avoid those risks.