In the message_user_info template search for this line
Code:
<xen:if is="{$user.isOnline}"><span class="Tooltip onlineMarker" title="{xen:phrase online_now}" data-offsetX="-22" data-offsetY="-8"></span></xen:if>
If it is not there then the template is your problem.