Dear @Evald Gruzdev ,
Glad to see that your issue had already been resolved and thanks for sharing the solution (really to be a certificate problem), so that others experiencing the same thing can easily reference this! Since the Microsoft Q&A community has a policy that "The question author cannot accept their own answer. They can only accept answers by others", I'll repost your solution in case you'd like to "Accept" the answer.
[Problem sending email]
Issue Symptom:
I have a problem sending emails to 1 particular domain. The error details are "mx2.economy.ge gave this error:
Must issue STARTTLS".
Solution:
Problem was solved by installing the same certificate on GFImailessentials server through IIS.
Best regards,
Jarvis