If you have My Sites and People searching I'm assuming you are running
MOSS 2007, not WSS. The WSS search  functionality is not used for
content in MOSS, only product help files. For content, you need to have
setup a Shared Service Provider and configured search sources and
crawls, and have done an indexing run.

WSS or SharePoint Server? If the latter, the wss_search_servername is only used
for help files.

in the shared Services providers properties, what database is specified in SQL?
SSP database name?

If WSS only, you don't really have people  search.

I have 3 open cases with MS on the same issue that have been esclated
to Redmond. By any change does this happen in seaching anything else
besides people? Choose modified by after your results showup and see
if you get the same message.

What OS are you on and is this 32 or 64

We had to build a new ssp and move the sites to the new ssp. We had
one or two issues caused by this (mysites needed to be fixed) and one
customized site had to have its local search  remapped. ALl search
functions had been down were working.

This entire thing happend after a day when the server stopped and had
to be rebooted.