First, I had this once and had to reset the index to clear it. That would be a
last ditch effort...
Does WSS_ADMIN_WPG have write access to c:\windows\tasks? If not, manual crawls
will work, but scheduled ones will not, however with a different sympton (just
bringing it up because there is an outside chance it is the same). If not
explicitly defined as having access, it would still work if your service
accounts were local administrators. I would check that one of those is true for
testing.
I am not saying to add all service accounts as local admins, btw...