A few ideas.
Ask them to speak more slowly or repeat it. It can be embarrising, but is effective.
Personally, as a native english speaker, I have found that if I 'listen' in the accent of a caller I can understand better.
I have a lot of Chinese, Indian & English (I'm Scottish!) customers calling me, if I mimic their accent in my head whilst listening I can often hear more clearly as the tonal qualities of regional or foreign accents can be understood more clearly & 'converted' into understood language, not just a bunch of sounds! It's worth a try! (Same way I learnt to listen to a foreign language & begin to separate the sound into individual words & piece together the important parts of a conversation - Dutch was fun!)