t() function doesn't translate strings inside node fields
Have a look at the options you can pass on to the t() function. You can explicitly say which language you want.

So you might do something like this to handle you message content :

$to_user = get_destination_user(); // whichever way you do that...
$body_content = t("!link started following you.",
                  array('!link' =&gt; $link),
                  array('langcode' =&gt; $to_user-&gt;language ));


In essence something like the above should do it.

Also make sure that the user language is set and valid. For this you might do something like :

$to_user = get_destination_user(); // whichever way you do that...

// get destination user language if set
$message_lang = !empty($to_user-&gt;language) ? $to_user-&gt;language : '';

// check if language is defined on our site
$languages = language_list();
if (!isset($languages[$message_lang])) {
    $message_lang = '';
}
// check if the language is enabled
if (!$languages[$message_lang]-&gt;enabled) {
    $message_lang = '';
}

$body_content = t("!link started following you.",
                  array('!link' =&gt; $link),
                  array('langcode' =&gt; $message_lang ));