This issue has been open for almost a year now, and a good patch is available: http://drupal.org/node/42826 To summarize the problem, if anonymous users do not have access to content in the primary links menu, they see "edit primary links". Without the patch, preventing this requires either disabling the primary links menu for all users or adding a link to which anonymous have access. I cannot see how this limitation in site design would benefit anyone.