Is there a recommended process for handling two people from different teams who cannot get along? Should I start with their managers, and work my way down? It seems like a simple problem that requires a simple solution, but the office politics involved makes it much more complicated than I anticipated. I have already attempted one on one meeting with both men, with no success.
Because you mention customer and vendor the situation is tricky as, depending on your specific situation, you likely have limited options in terms of confronting guys and working this through with them.
Either way I would start with understanding what are the sources of the clash. I would talk individually with the guys not to straighten things up but to learn what their problems are. Commonly it's not an answer you're going to get instantly and you'd need to dig deeper. Techniques like 5 whys may come handy in the process.
You may or may not have complete knowledge about the issue when you're done talking. I'd even say that the latter is more likely. Either way you probably heard two different things or two different interpretations of the situation. If you can find common ground with the guys it's the best place to start. In this case you can show them potentially beneficiary way for both of them.
However, it may not be that easy. By this point you could have heard two completely different stories with basically no common points whatsoever. In such case some kind confrontation would be needed to move further. As harsh as it may sound in such situation sometimes you need make things worse to make them better later.
The trick is to facilitate the meeting in a way that it follows a constructive path. How you do that is a completely different story, but basically what you want to do is be a neutral arbiter, who isn't choosing a side, but is calling foul every time they see it. If the discussion is dominated by one side it's your job to create a space for the other to state their points as well.
The whole thing with the meeting is that it's way easier for us to complain, pursue conflict or even fight if we don't do it face to face. It's easier to go with angry email than stating the same thing personally in their faces. The only risk is, that in the middle of hot discussion we tend to get carried away, and this is why facilitator's job is crucial here.
Hopefully this will allow you to make the way out of the situation. Of course your goal should be to find a solution which is at least satisfactory to both parties. Otherwise chances that it will be respected are thin. Note: you don't aim to see the guys love each other but to cooperate with each other professionally. Nothing more but nothing less.
If the method fails it's time to escalate things to managers of these folks. I definitely wouldn't start with escalation as using it as default solution would only make the situation more difficult to solve. After all, no one likes to see people complaining about them to their boss. If the escalation happened from this point it's more responsibility of respective managers, although it's always worth to monitor the situation and remind people about their jobs if they don't do it.
Remove the people from the situation (in your mind) and try to understand the situation for what it is. Understand what the project-related issue is that requires the two to interact with each other. Address the issue. If that doesn't work, try to find alternative ways that the two can interact more productively. Do not attempt to resolve any personality conflicts. Your job as a project manager is to get the project-related task done. Not to facilitate friendships. Trying to get the job done with impartiality and fairness is best achieved by letting the task dictate the action rather than the people.
Try to find out the problem behind the problem you are observing. Like the tip of an iceberg, the behaviour you see is motivated by many invisible factors.
With the right questions and enough empathy you might get down to the real problem. Going top down via management could make matters worse.