Recently we started getting following errors in CRM 4.0 outlook client while tracking any email or setting regarding for any email in outlook.
Error 1
“An error occurred promoting this item to Microsoft Dynamics CRM. The Microsoft Dynamics CRM server count not be contacted or the user has insufficient permission to perform this action”
Error 2
“The Requested record was not found or you do not have sufficient permission to view it”
Solution
Based on this KB Articles , following are steps to resolve this issue.
Step 1: Clear the outlook cache as specified in following screen print.

Note: these steps are for outlook 2010.
Step 2: clear down IE Temporary files as mentioned in following steps.
1.Open IE- > go to Tools -> Click Internet Options
2. On Browsing history section, click on Delete and then delete all the IE temporary data.
Once above steps are done, close your outlook and then start again.
Hope this helps!!!
Cheers,
MayankP