iMessage no longer able to reach a specific contact
The reason it was broken: the specific contact had changed his AppleID password and had not updated it on his iPhone.  

The solution that worked for us:


He reset his AppleID (c.f.: http://support.apple.com/kb/ht5624)
He updated the password at iPhone (iOS7) >> Settings >> Messages
He updated the password at iPhone >> Settings >> FaceTime
I reset my network settings: my iPhone (iOS7) >> Settings >> General >> Reset >> Reset Network Settings


He didn't have to reset his network settings, and neither of us powered our iPhones off/on.