It can take a while and its possible things can go wrong. If no index files exist when you doa search it will kick off a task to rebuild it, it first writes to the database in the mp_IndexingQueue, after that it starts a task on a background thread to process that queue in sequence creating/writing to the index.
So if timing is not just right, and another search is made before the first indexed files appear it can get out of sync and out of step because it may start another round to try and build it whhile it was just getting ready to write the files.
It will always log at least one index error when you rewbuild because at first the index doesn't exist so it traps that error and logs it then creates the index.
If things get out of wack you need to:
1. recycle the app
2. clean out the mp_IndexingQueue and mp_TaskQueue tables again and retry with the rebuild button or by delete/search
Once it is running leave it alone and give it 10-15 minutes. You can watch the log while it runs but don't do searches until its done.
if the app pool is already recycling frequently it could also cause some problems with writing to the search index. It should be able to resume but its dodgy because recycling the app kills tha background thread that is doing the work.
Its also possible to rebuild an index on a different machine with a copy of the site and db that is up to date and then upload the index files removing any that are already there. I've done it before but its best if it can be built right on the site.
Hope it helps,
Joe