Style tabs/links that anon can't see
menu_local_tasks() is a good place to start looking. This calls theme_menu_item_link() which is the pertinent theme function to look at. It makes sense to do any access checks in the preprocess and you'll also need a custom theme function to handle the variables you set. You mention user_access() in the Q, but it's important to remember that the access callback could by any function. For that reason it's necessary to impersonate the anonymous user (note the link isn't specifically for anon users, but the fundamentals are the same). You can get the menu item type, access callback, and access arguments from $link. The bit of code to do the actual checks would look something like:

if ($menu_item_type &amp; MENU_LOCAL_TASK) {
  global $user;
  $original_user = $user;
  $old_state = session_save_session();
  session_save_session(FALSE);
  $user = drupal_anonymous_user();

  if (!call_user_func_array($access_callback, $access_arguments)) {
    // Anon's don't have access to this local task
  }

  $user = $original_user;
  session_save_session($old_state);
}


A note regarding performance: none of the calls access the database, except possibly the access callback (which could do anything). user_access() caches a role's permissions, so that would only access the DB the first time. Other access callback's might not do this. It wouldn't be particularly difficult to cache the results of the access callback yourself (keyed by access callback and serialised arguments).