Seeing as my Russian, Ukrainian, Belarusian, Mexican, French Canadian, and Brazilian coworkers don't seem to have these issues with me I don't think the issue is with my explanations.
The problem likely lies deeper than just the accents; and by the way, the English requirement (including a verbal test) is already set in place for most of the workers. The regular halfway-decent ones will likely already have TOEFL scores hovering around at minimum the high 100s, and in the non-university hiring pipelines I have seen, the English/ESL tests seem to be common if you are not from an English-speaking country, so if you are seeing people where nobody can understand what they are saying, you need to take a better look at your employer's hiring practices.