Our experiences with GitLab have been really positive. GL may not be on par with GHE UX wise, but I don't really feel that this has been an issue for us. Coming from GH or GHE, GL is a little more difficult to navigate, but it's getting better with each release. The thing that probably bugs me the most is the home page for a repository being the activity stream. However, considering that we're saving $25k per year by using GL over GHE, I can happily put up with it.
I've never encountered the search issue you describe. We're using the latest GL, perhaps it was a problem with an older version?