This is hopefully a quick tweak that can be made to improve engagement....
On the users listing page (URL provided if needed), only the 'Follow User' and 'Add as Friend' buttons show to non-logged as default... the 'Message' button only appears next to them when you're logged in.
For the same reason the 'Follow' and 'Add Friend' buttons show to non-logged in users (to draw people in to logging in), the 'Message' button should as well?
Thanks!