Your users need "read" privileges on Leads, Accounts and Contacts - even if the business rules dictate that they shouldn't have read privileges on all of these entities. For example, if you remove "Read" privileges on Leads from the Security Role for these users, when Outlook tries to scan the MS CRM database for a matching email address to regard the message to, it can't access the leads.
NOTE: If you don't want your users to be able to view Leads in the navigation even though you've given them read privileges on this entity, you can edit the sitemap and either totally remove the links for Leads or restrict it using a privilege tag in the sitemap such as the following which only makes Leads visible in the left nav if the user's security role also permits them to execute Quick Campaigns.
<
SubArea Id="nav_leads" Entity="lead" DescriptionResourceId="Lead_SubArea_Description" >
<
Privilege Privilege="AllowQuickCampaign" />
</
SubArea>
