I'm not a native English speaker but I do understand your frustration. Here are some of my experiences:
Embrace the elephant in the room
Time to time I found people around me are too "polite" to not tell me that they don't understand what I say. I have had a course evaluation saying that "the instructor is great but time to time I had hard time understand some words he said. For example, it took me a few weeks to realize he meant 'result' when he said 'ray-sult'." I was actually amazed by how much money this student spent to be confused.
Now, at the beginning of the course, I surrender myself and introduce the elephant. "I have accent, and if any of my pronunciations is off, you're more than welcome to correct me. Your input will help me to become a better speaker." Then move on.
I think the situation is the same in the native speaker's shoes. If you have trouble understanding a colleague. Tactfully ask for a few repetitions in an informal conversation, and then confess that you sometimes may not catch the full gist of the speech, and proceed to ask for a blanket excuse in the future should you need another repetition again.
"Fully understand" is likely an illusion
Your point about missing important materials in conference is well taken. Here are two reflections I have: i) realize that even you get the whole sentence, it's still a foreign language to the speaker and there will always be some loss in translation. ii) In a conference, it's probably hard to pick up all the little bits of information. On this point, you can Zen that over like watching a firework; let that go. Or if the curiosity is killing you, approach the speaker after the talk and clarify. If the conversation goes well you can consider exchanging business cards, and ask for a copy of their presentation over the e-mail.
Hold on to an ad hoc interpreter
When I teach in foreign countries, there would be English speakers whose speeches are beyond my cognitive reach. This is how I deal with it: i) Keep smiling, and rephrase the question as best as I can, and I know I'd fail, then repeat step i) for a few more times and keep calm and smiling, ii) eventually some participants who are more proficient would volunteer to translate. If no one does, embrace the elephant in the room and say "I guess I'm a bit stuck here, would anyone tell me what I missed in the question?" iii) once the question is clarified, answer it, facing the original questioner. For myself, I prefer to slowly pace up to the board, and write down my talking points. I think this would enhance the questioner's understanding if he/she has trouble listening to my speech.
Often enough, no one would help. And the questioner may just wave his/her hand and give up. Don't be frustrated. Invite the person to stay and talk, and perhaps then you can employ things like paper and pen to better understand each other.
Use writing
When communicating with colleagues who have heavy accents, I'd also rely a bit more on writing. Using e-mails, or using a white board in a meeting may help. On that note, I also bring a stack of index cards with me to meetings and classes.
Use international "language"
Smile, drawing, ... etc. are always good substitute or supplement to verbal communication. Avoid using very specific body gestures because one friendly gesture here may deem insulting in another culture.
Learn some foreign languages
It's actually quite interesting that comparing to my colleagues who are native speakers, I actually have an easier time filtering other countries' accents. I attributed to the fact that when sitting through English classes, our teachers put extra emphasis on highlightin how our mother tongue may cause some English words to be mispronounced. Then in university I picked up a couple foreign languages, and then now I have virtually no problem listening to people from those countries speaking English.
It may actually be impractical to learn all the languages. Here are a couple tricks I have used: First, just learn their basic pronunciation system first and if you have time, figure out how to say some basic general words. In the process, evaluate how the system may work if it's used to pronounce English. For example, Japanese system does not differentiate r and l, so you may expect hearing "running" and "learning" or "lighting" and "writing" pronounced identically. Mandarin does not have the -th and Th-, so Mandarin speakers may compensate with -ve and F- (e.g. A "fief" instead of a "thief".) On the contrary, Mandarin has an elaborated series of s or s-like sounds: si, zi, and ci, with different tongue-teeth positions and amounts of air blowing through the lips. So, you may expect emphasis on some syllables that would have been only lightly pronounced if spoken by a native speaker. Italian speakers, on the other hand, tend to clearly pronounce syllable-by-syllable and attach an -e or -a after some words. Once we put the same nouns spelled in English and Italian side by side, the reason would become apparent.
Second, read some books on how to get rid of accents or how to speak in British and American accent. Most of these books would have a chapter or so dedicated to explain major mistakes made by speakers from different systems. For example, Japanese speakers may have an extra "-gu" after all words ending with -ing; Chinese speakers may not distinguish clearly between -s and -th. These tips are not for native speakers, but by learning some major traits, native speakers can quickly filter the noise and get to the content.
Make an effort
It takes time to understand accents. But as you speak to a certain foreign person more and more, you should be more at ease. This is particularly important when dealing with your colleagues. Keep talking and keep categorizing their speech traits, and you'll get better at talking to them. Most of these advices may make you feel vulnerable or even stupid, but as an ESL and also a foreign language learner, when it comes to language, I think we cannot be overly reserved.
