Here's my solution, using Buddypress:
function page_title()
{
qa_html_theme_base::page_title();
if(!empty($this->content['form_activity'])) {
$handle = preg_replace('/<[^>]+>/','',$this->content['loggedin']['data']);
$this->output_raw('<h2 style="padding-top:0"><a href="'.apply_filters( 'bp_get_send_private_message_link', wp_nonce_url( $bp->loggedin_user->domain . $bp->messages->slug . '/compose/?r=' . $handle ) ).'">send message</a></h2>');
}
}
This puts a "send message" link below the "User <name>" title on the user's profile, linking to the Buddypress private message compose tab. If you use a different WP plugin for private messages, it would probably be easy to fix up.