Quick Navigation (or Quick Search) loads indefinitely

We've reindexed the application. When I start typing a value in the Quick Navigation box, results in an icon depicting a loading circle, yet no results are ever shown. Upon pressing ENTER, a list of results is shown almost immediately.

Something appears to be wrong with the Quick Navigation function. Perhaps a REST call is sent but never receives an answer? I guess a time-out message or something could be useful.

Anyway, we would really like to see the Quick Navigation restored to its former glory, as searching via the regular search pages costs us more time and is therefore less efficient.