I had search issues as you have, as well as others. We had installed
SPS on a member server using an Domain OU admin account. The down
side to this was that the password gets changed every 15 days so I
created a new SPS admin account and then I systematically changed
all access accounts in the portal, IIS application pools and the SQL
dbs. This fixed the problems for me.