We encountered a daily error reported by the deletion service as follows:
Error: Deletion Service encountered an internal error for
Exception: System.Data.SqlClient.SqlException (0x80131904): Timeout expired. The timeout period elapsed prior to completion of the operation or the server is not responding.
Error: Deletion Service failed to clean up the PrincipalObjectAccess table for
Exception: System.Data.SqlClient.SqlException (0x80131904): Timeout expired. The timeout period elapsed prior to completion of the operation or the server is not responding.
The deletion service was scheduled to run at 7 AM at the start of the core business hours and that error caused strange CRM outage in which CRM is showing 404 directory not found error without any further errors thrown on the front end servers.
The first quick resolution we applied by modifying the deletion service scheduled execution time using the great tool CRM 2011 Job Editor
Second resolution which take around a month with Microsoft premier support was to clear the table named [SubscriptionTrackingDeletedObject] in the CRM organization database, you need to make sure before clearing that table that all users using CRM for Outlook are in Online mode at that time (that in case you are using the offline mode in your company) and that made the magic and stopped the deletion service error.