We had a very similar experience with Gitlab too.

Our teams evaluated Gitlab for a year before completely migrating away from it (to Github Enterprise for SCM, Confluence for wiki, YouTrack for issues and TeamCity for CI).

Not a single team (out of 20) was happy with the overall performance (and especially the performance of code search).

As far as wiki is concerned, Confluence's UI has its own share of issues, even after their recent overhaul, but all in all it is much better product. YouTrack and TeamCity are simply much more polished & stable products and are (in our experience) easier to administer than the competing offerings from Gitlab.