That is the expected behavior. If no files exist it should re-build index on first search. This task is queued on a new thread so it doesn't hold up the current page request.
It still seems it can't create files for the index or the log. However I have no explanation why File Manager works. It still points me to some kind of funky permission issue.
Wish I had more help, but thats all I can come up with.