It was indeed, Modern Warfare. This was back in 2007 so it had just launched and when I mentioned maybe Skypeing we both found we already had headsets and played most nights anyway so we just set up a private chat and shot at each other.
Wow. This is the most unique setups I've heard. I did hear once about a person who got an internship at Facebook (if I recall correctly) over online in-game chat.