I never could get it to work cleanly using the KB info about the Kerberos issues / workarounds.
What I use (and has been working fine for years now) is to create a SQL Login and use SQL Server Authentication vs Windows Authentication. Within the Linked Server configuration, use a user account that has admin rights to the catalog server.
I tried to update this to use Windows Search on 2008 server, but never could get the query to work from MSSQL. From what I read, its not supported. But, if someone has it working - please pass along the details.