Jake's code change above works great. Just change the bit after => to true (in the file library/XenForo/ViewPublic/Helper/Message.php), all links are then nofollow including admin and mods.
ok i know this is old but does this changing all links to no follow affect my own inner pages. I ran a test on my site and it shows this as no follow
<a href="find-new/posts" rel="nofollow">Recent Posts</a>
<a href="find-new/posts?recent=1" rel="nofollow">Recent Posts</a>