Anonymous users can't use personal contact forms
Assuming that the anonymous users are not trying to access user/0/contact (which would not be an ordinary case), the reasons why they cannot access the contact for a an authenticated user A are essentially 3:


User A didn't enable the contact form
The setting for enabling the contact form for user A has not been yet saved
The anonymous user sent too much messages


In the first two cases, it's the access callback for the user's contact form that block the access, using the following code. (See the comment before the code.)

// If the requested user has disabled their contact form, or this preference
// has not yet been saved, do not allow users to contact them.
if (empty($account-&gt;data['contact'])) {
  return FALSE;
}


In the third case, it's the form builder that returns an access denied page.

// Check if flood control has been activated for sending e-mails.
  $limit = variable_get('contact_threshold_limit', 5);
  $window = variable_get('contact_threshold_window', 3600);
  if (!flood_is_allowed('contact', $limit, $window) &amp;&amp; !user_access('administer contact forms') &amp;&amp; !user_access('administer users')) {
    drupal_set_message(t("You cannot send more than %limit messages in @interval. Try again later.", array('%limit' =&gt; $limit, '@interval' =&gt; format_interval($window))), 'error');
    drupal_access_denied();
    drupal_exit();
  }


Notice that in last case, the default limit is 5 messages in a hour, and that limit is cumulatively valid for any user sharing the same IP, as flood_is_allowed('contact', $limit, $window) executes the following code.

if (!isset($identifier)) {
  $identifier = ip_address();
}


If you are not seeing any error message from Drupal ("You cannot send more than […]") and the enabled theme or any module is not hiding the error messages, I would assume the users didn't enable their contact form, or the setting to enable the contact form was not yet saved.