I'm seeing the same thing on an all-in-one setup (SBS 2011). I've got SP1 RU3-v3 installed and have followed the procedure in this blog posting. I verified that I saw event 109 at the start of the index rebuild process and event 110 when it completed. However, even after following this process, I am still seeing the same errors.
Search in OWA fails with the message "The action couldn't be completed. Please try again." and causes event 9877 to be logged with an error code of 0x80043629. Running the Test-ExchangeSearch cmdlet also generates event 9877 with an error code of 0x80043629. The Test-ExchangeSearch cmdlet fails with an error of "Time out for test thread.".
I am also seeing intermittent occurrences of event 9842 with an error code of 0x80041820.