Spotlight re-indexing takes too long or doesn't work
OK, I solved it, it seems... 

The Solution

Run 

sudo /System/Library/Frameworks/CoreServices.framework/Frameworks/LaunchServices.framework/Support/lsregister -kill -seed -lint -r -f -v -dump -domain local -domain system -domain user -domain network

killall Dock

sudo mdutil -E /


Not sure if all of these are needed, but that's what worked for me. The first command resets the Launch Sservices Database, the second one resets the Dock, and the third one triggers Spotlight reindexing. 

Note that before that I tried running 

/System/Library/Frameworks/CoreServices.framework/Versions/A/Frameworks/LaunchServices.framework/Versions/A/Support/lsregister -kill -r -domain local -domain system -domain user


instead of the first command, and it didn't help. To be more precise, it seemed to have fixed search, but not spotlight.

I also tried sudo rm -R .Spotlight-V100/ suggested in the comments to the question, but it didn't help either.

Details

the issue was in the Launch Services Database. I figured it out by looking at the Console app. There were tons of messages like 

errore  16:19:03.743202 +0100   mds LaunchServices: store or url (null) was nil -10813, retrying
errore  16:19:03.743247 +0100   mds LaunchServices: Database mapping failed with result -10813, retries = 7


I found this thread, which led me to trying to reset the Launch Services Database. First I tried the command above that failed. Then I found a fuller (it seems) version of that command, which is posted in the first code block in the "Solution" section above.