Joyce Wycoff suggests taking internal stakeholders to lunch:

Identify all of your stakeholders … the people who are affected by your work, immediately and at a distance.  Your monthly report may only go to 3-4 people but the information in it may get passed along or acted upon by dozens of others.  Start to invite your stakeholders to lunch one or two at a time and just get to know them.

This is great advice, and equally applicable to the stakeholders in your clients' organizations.  Just make sure they know you are not billing them for the lunch!