SharePoint 2010 Search Error 0x800703fa

We have migrated from SharePoint 2007 to 2010. Everything appears to be working correctly except for an intermitent error with search. Occastionally search results will crash for all of our sites and when we look up the coorliation id we get the following error:

Exception when fetching results: System.ServiceModel.FaultException`1[System.ServiceModel.ExceptionDetail]: Illegal operation attempted on a registry key that has been marked for deletion. (Exception from HRESULT: 0x800703FA) (Fault Detail is equal to An ExceptionDetail, likely created by IncludeExceptionDetailInFaults=true, whose value is: System.Runtime.InteropServices.COMException: Illegal operation attempted on a registry key that has been marked for deletion. (Exception from HRESULT: 0x800703FA)   
 at System.Runtime.InteropServices.Marshal.ThrowExceptionForHRInternal(Int32 errorCode, IntPtr errorInfo)    
 at Microsoft.Office.Server.Search.Query.KeywordQueryInternal.Execute()    
 at Microsoft.Office.Server.Search.Query.QueryInternal.Execute(QueryProperties properties)    
 at Microsoft.Office.Server.Search.Administration.SearchServiceApplication.Execute(QueryProperties properties)    
 at SyncInvokeExecute(Object , Object[] , Object[] )    
 at System.ServiceModel.Dispatcher.SyncMethodInvoker.Invoke(Object instance, Object[] inputs, Object[]& outputs)    
 at System.ServiceModel.Dispatcher.DispatchOperationRuntime.InvokeBegin(MessageRpc& rpc)    
 at System.ServiceModel.Dispatcher.ImmutableDispatchRuntime.ProcessMessage5(MessageRpc& rpc)   

We reset IIS and the problem resolves itself for a while. Has anyone come across a perminant fix for this?