My first thought to a situation like this is... Service account password
expired.

I've seen such error  a few times before but can't say that the root
cause and the fix  were all the same. One case indeed had to do with
either expired account or missing permission (SQL Server?).

On a recent situation, only when you search  "This Site" or "This List"
scope, you get this error but if you search using "All Sites" or
"People", it works OK. So, I guess this has more to do with WSS search
service than Office SP Search one. I have not been able to get a server
admin to look in further yet. Would that be your thought as well?

I checked the service  accounts and they are OK.

Strangely, the search  in the production environment (no SP1) is now working
after we reset  the services  and reboot servers  the second time.

But, the Search in the Dev environment (which has WSS SP1 and MOSS SP1) still
get "The search request  was unable  to connect  to the Search Service" error.
We are running in a small MOSS farm (with Kerberos) configuration with 1 SQL and
2 WFE servers.

I have had issues with post SP1 systems if the service  pack was not applied
"just right". When installing SP1 you need to install the service pack for
WSS first, exit out from the Configuration wizard, run the server SP1 and
get to the point where the wizard runs and informs you to get that far on
all your servers. Then, on the server running your Central Administration,
complete the wizard and once it has finished , complete the wizard on your
other servers.

Do you know the process, and account under which the service pack was
applied?

I installed the SP1 (both WSS and MOSS) on the WFE servers  as instructed in
technet.microsoft.com/.../bb735839.aspx
using the admin account. I also am a local administrator on these servers.

I did a quick check after the SP1 installation and the Search Service worked
fine.

That was a couple weeks ago. I didn't get any report of Search errors from users
until yesterday.

I'm scanning the MOSS log files now for any hints. Do you know any key word for
which I should look?