What I would do is:
1 clear your log
2 delete all rows from mp_IndexingQueue and mp_TaskQueue
3 delete all contents of the index folder again
4 type a space in Web.config and save it to recycle the app
5 clear the log again
6 do another search to rebuild the index again
7 wait 5 or 10 minutes and search again
We changed recently from serializing tasks and index queue items as soap to serializing them as xml because the SoapFormatter doesn't work in medium trust. I think you still have some rows serialized as soap and so it errors on trying to deserialize it as xml
Hope it helps,
Joe