I hacked it. I have next to no knowledge of php so I doubt it's the best way. It was arrived at by trial and error. For anyone interested, I removed the 'contact' link for people not logged in by replacing this code:

| {/if}<a href="index.php?mode=contact" title="{#contact_linktitle#}">{#contact_link#}</a>

with this:

{/if}{if $user} | <a href="index.php?mode=contact" title="{#contact_linktitle#}">{#contact_link#}</a>{/if}

in templates/default/main.tpl

Thanks Alex