OnPremise GitLab EE Navigation Search not finding repositories in search results

Summary

In our on premise GitLab Enterprise Edition 12.3.5-ee
where we recently migrated many repositories from a bare repository to the new GitLab.

When searching from the navigation var by a name like 'vodafone' and pressing enter, it takes you to:
http://our-company-gitlab.com/search?utf8=✓&search=vodafone&group_id=&project_id=&repository_ref=&nav_source=navbar

Where nothing is found! The page results shows 0 results found.
But in our company we do have projects and sub groups with that name!
Example:
SomeGroup / SomeSubGroup / SomeSubGroup2 / UK / UK_VODAFONE_PROJECT
SomeGroup / SomeSubGroup / SomeSubGroup2 / US / Vodafone / OurWebProject
SomeGroup / SomeSubGroup / SomeSubGroup2 / US / Vodafone

When looking for what repositories we have with that word we expected GitLab to at least find the above results, but nothing was found!
These repositories were recently imported to our in premise GitLab and no commits were done directly in Gitlab other than importing the existing repo.
Only after adding some details to those repositories they started to appear in the search.

Now we can't be sure after using GitLab search, if we really don't have repositories under the searched name.

Steps to reproduce

(How one can reproduce the issue - this is very important)

Example Project

(If possible, please create an example project here on GitLab.com that exhibits the problematic behavior, and link to it here in the bug report)

(If you are using an older version of GitLab, this will also determine whether the bug is fixed in a more recent version)

What is the current bug behavior?

(What actually happens)

What is the expected correct behavior?

(What you should see instead)

Relevant logs and/or screenshots

(Paste any relevant logs - please use code blocks (```) to format console output, logs, and code as it's tough to read otherwise.)

Output of checks

(If you are reporting a bug on GitLab.com, write: This bug happens on GitLab.com)

Results of GitLab environment info

Expand for output related to GitLab environment info

(For installations with omnibus-gitlab package run and paste the output of:
sudo gitlab-rake gitlab:env:info)
(For installations from source run and paste the output of:
sudo -u git -H bundle exec rake gitlab:env:info RAILS_ENV=production)

Results of GitLab application Check

Expand for output related to the GitLab application check

(For installations with omnibus-gitlab package run and paste the output of:
sudo gitlab-rake gitlab:check SANITIZE=true)
(For installations from source run and paste the output of:
sudo -u git -H bundle exec rake gitlab:check RAILS_ENV=production SANITIZE=true)
(we will only investigate if the tests are passing)

Possible fixes

(If you can, link to the line of code that might be responsible for the problem)