While I was trying to setup MOSS 2007 on a single server box I had this problem of Invalid Password or User Account not found problem when I try to start the Windows SharePoint Search Service.
I have a user account something like: aifsmoss\searchspccontentaccessusr which I was trying to use while setting up the WSS search service using the Central Administration. Even though I give the correct user name and password it shoots back saying invalid password or account. After a couple of days of troubleshooting I was able to figure out that in the Active Directory, in the user account properties the pre-windows 2000 account name is truncated and it looks something like: aifsmoss\searchspccontentacce
so basically the length of the user account name is the problem and it is truncated. I created another user account and it worked just fine.
Below is the screen shot of the user account properties.