Verify the search  service account is a local administrator.

(for the security conscience folks - If that scares you, you have COM
security work to do)

I've verified that it is.

If that were the case, wouldn't there be an authentication failure
recorded in the logs somewhere?

Flip on the indexer  logs from stsadm.exe...

Stsadm.exe -o listlogginglevels -showhidden and find what you want to
log.

Then, stsadm.exe -o setlogginglevel -category <insert category>
-tracelevel <level> -windowslogginglevel <level>

Try setting them to Verbose and Information. Your trace logs are in the
12 hive, windowslogging in eventvwr.exe

Here's where the failure seems to be occurring:

05/16/2007 09:20:38.56 w3wp.exe (0x0488)
0x00D0 1624
8acf Verbose Current user  after SqlConnection.Open: Name:
<DOMAIN>\<FarmServiceAccount> SID: S-1-5-21-10639774-1603079040-
1461932148-5040 ImpersonationLevel: None

...
Some COM access lines...
...

05/16/2007 09:20:38.61 w3wp.exe (0x0488)
0x00D0 Search server  Common MS search  Administration
7xz5 High
Modifying ACL to allow <DOMAIN>\<FarmSearchAccount>' R/W access
to 'C:\WINDOWS\Tasks' and to remove access for WSS_WPG...

05/16/2007 09:20:38.61 w3wp.exe (0x0488)
0x00D0 Search Server Common MS Search Administration
7pjy High
Modifying ACL to allow '<DOMAIN>\<FarmSearchAccount>' R/E access to
the BIN folder 'D:\Program Files\Microsoft Office Servers\12.0
\Bin'...

05/16/2007 09:20:38.65 w3wp.exe (0x0488)
0x00D0 Search Server Common MS Search Administration
0 High The call to SearchServiceInstance.Provision
(server '<WFE>') failed. Setting back  to previous status 'Disabled'.
System.InvalidOperationException: Method failed  with unexpected  error
code 3. at
System.Security.AccessControl.NativeObjectSecurity.CreateInternal
(ResourceType resourceType, Boolean isContainer, String name,
SafeHandle handle, AccessControlSections includeSections, Boolean
createByName, ExceptionFromErrorCode exceptionFromErrorCode, Object
exceptionContext) at
System.Security.AccessControl.FileSystemSecurity..ctor(Boolean
isContainer, String name, AccessControlSections includeSections,
Boolean isDirectory) at
System.Security.AccessControl.DirectorySecurity..ctor(String name,
AccessControlSections includeSections) at
System.IO.DirectoryInfo.GetAccessControl(AccessControlSections
includeSections) at
Microsoft.Search.Administration.Security.FileSystem.EnsureACL
(DirectoryInfo directoryInfo, String username) at
Microsoft.Office.Server.Search.Administration.SearchServiceInstance.Pr
ovision() at
Microsoft.Office.Server.Search.Administration.SearchAdminUtils.DeployC
redentials(SearchServiceInstance localSearchServiceInstance, Boolean
deployOnlyLocalInstance)

I interpret this to mean that the failure occurs when it tries to set
the ACL of the 'D:\Program Files\Microsoft Office Servers\12.0\Bin'
folder (and not on the previous object(s)).

I've checked the security of the Bin folder. Administrators have full
control (of which the farm service account is a member). The search
service account had R/E. WSS_ADMIN_WPG has full control, and WSS_WPG
has R/E.

Effective permissions for the Search and Farm service accounts are
full control.

I've even tried (temporarily) setting DOMAIN USERS / Full Control on
the parent folder to no avail. I checked for deny permissions, and
there are none. I must be barking up the wrong tree?

Try the farm account (central admin  app pool ident) for the search
service identity. All service accounts must have admin access anyway, so
it shouldn't matter. Do not change the default content access account to
this.

You should change the service account from central  Admin - Farm Topology
- Office sharepoint  Server search  (hyperlink), and not in Windows
Services.

If that works, then you can leave it ( I use the same account for all
services) or figure out the search service account.

If not, I would honestly call PSS and let us know the problem.