What permissions does the user who is searching have? Is the email address publicly available or private?
If the users email is private, then unless the user who is searching has admin privileges you cannot search via email. It would have to be publicly available.
Also to search via email address, you are using the wrong field:
https://gitlab.example.com/api/v4/users?email=user@gmail.com
this works if the email is private, and the API user has admin privileges, or if the email is publicly available, and the user has standard privileges.
Also explained here in previous posts: Retrieve User Emails VIA API - #4 by iwalker