Boris, don't get frustrated with what you are experiencing. Email overall in China is a mess and unreliable. Due to all the spam many ISPs in USA/Europe block whole ISPs IP address block (very often with racial motivations). 126.com gets blocked a lot also. So far in 6 years our users have not had any problems in China, but I guess we are lucky and are not on the radar.
Don't get frustrated, there are lots of people out there feel the same way as you do having the same issues.. I conducted a survey in a trade fair in GZ a few months ago, and I found about less than 5% were happy and trouble free.
The problems with SMTP are often due to the email scanning farms run by the security service get overwhelmed...
Have you tried to do a traceroute on port 25 or what ever smtp port you should be using?