This is a problem with inconsistent databases:

Please try:

RESOLUTION/WORKAROUND:
====================
- First we need to find out which databases are currently not
synchronized, this can be done from a simple stsadm command on your
web front end.

stsadm -o sync -listolddatabases n (n= number of days since when
databases are not synchronized)

- Run following command for all the ID's

stsadm -o preparetomove -contentdb sqlserver:dbname -oldcontentdb <GUID>

where sqlserver is where your content is housed,
dbname is any database in your farm,
GUID is a guild from the list of non-syncing databases we generated
with the command above.

- Based on your crawl schedule wait until the next full crawl. Once it
completes go back into your MOSS server  and run the
stsadm -o sync -listolddatabases n command again

-Anything left can likely be removed at this point. You can
remove what is left by running the following command:

stsadm -o sync -deleteolddatabases n - this will delete all GUID
entries in the SSP for anything that is out of sync for more than 5
days.

You have now successfully cleaned all inconsistencies with
synchronizing in your SSP.

I tried your solution below but i am still getting these errors on my
second WFE server  and search is still not working. Any other thoughts?

Event Type: Error
Event Source: Office SharePoint Server
Event Category: Office Server Shared Services
Event ID: 6482
Date: 11/26/2008
Time: 11:52:54 AM
User: N/A
Computer: D01SVR507
Description:
Application Server Administration job  failed for service instance
Microsoft.Office.Server.Search.Administration.SearchAdminSharedWebServ
iceInstance (851fa22c-cbd5-4c27-a236-0c994d434626).

Reason: The specified account name is invalid.
Parameter name: account

Techinal Support Details:
System.ArgumentException: The specified account name is invalid.
Parameter name: account --->
System.Security.Principal.IdentityNotMappedException: Some or all
identity references could not be translated.
at System.Security.Principal.NTAccount.Translate
(IdentityReferenceCollection sourceAccounts, Type targetType, Boolean
forceSuccess)
at System.Security.Principal.NTAccount.Translate(Type targetType)
at
Microsoft.Office.Server.Utilities.WindowsSecurity.ValidateAccount
(NTAccount account, Boolean throwIfInvalid)
--- End of inner exception stack trace ---
at
Microsoft.Office.Server.Utilities.WindowsSecurity.ValidateAccount
(NTAccount account, Boolean throwIfInvalid)
at Microsoft.Office.Server.Administration.SharedAccessRule.Validate
()
at
Microsoft.Office.Server.Administration.SharedComponentSecurity.SetAcce
ssRule(SharedAccessRule accessRule)
at
Microsoft.Office.Server.Administration.SharedComponentSecurityFormatte
r.DeserializeFromXml(XmlReader xmlReader, SharedComponentSecurity&
security)
at
Microsoft.Office.Server.Administration.SharedComponentSecurityFormatte
r.FromXmlString(String xml)
at
Microsoft.Office.Server.Administration.SharedResourceProvider.Internal
GetAccessControl()
at
Microsoft.Office.Server.Administration.SharedResourceProvider.GetAppli
cationSecurity()
at
Microsoft.Office.Server.Administration.SharedWebServiceInstance.Provis
ionSharedResourceProviderWebConfigSettings(SharedResourceProvider srp)
at
Microsoft.Office.Server.Administration.SharedWebServiceInstance.Synchr
onize()
at
Microsoft.Office.Server.Administration.ApplicationServerJob.ProvisionL
ocalSharedServiceInstances(Boolean isAdministrationServiceJob)

I've seen this before, in our case it wanted us to use the fqdn either
domain\name or server\name for the local account.