After spending several hours investigating how search functionality in User Manager works and doing some "shaman dancing" around it, I ended up with a solution that requires to override a standard Sitecore.Security.Accounts.UserProvider and change its method called "GetUsersByName". As it turned out, search functionality of User Manager calls the GetUserByName method when one searches for a user.
This is how it looks:
namespace Sitecore.SharedSource.Security.Accounts
{
    public class UserProvider : Sitecore.Security.Accounts.UserProvider
    {
        protected override IEnumerable GetUsersByName(int pageIndex, int pageSize, string userNameToMatch) 
        {
            return FindUsers(pageIndex, pageSize, userNameToMatch);
        }
        protected IEnumerable FindUsers(int pageIndex, int pageSize, string userNameToMatch) 
        {
            Assert.ArgumentNotNull(userNameToMatch, "userNameToMatch");
            IEnumerable users = null; 
            string userWithNoWildcard = StringUtil.RemovePostfix(Settings.Authentication.VirtualMembershipWildcard, StringUtil.RemovePrefix(Settings.Authentication.VirtualMembershipWildcard, userNameToMatch));
            if (Regex.IsMatch(userWithNoWildcard, @"^([0-9a-zA-Z]([-.\w]*[0-9a-zA-Z])*@([0-9a-zA-Z][-\w]*[0-9a-zA-Z]\.)+[a-zA-Z]{2,9})$"))
            {
                users = findByEmail(pageIndex, pageSize, userWithNoWildcard);
            }
            else
            {
                users = findUsername(pageIndex, pageSize, userNameToMatch);
            }
            return users;
        }
        protected IEnumerable findUsername(int pageIndex, int pageSize, string username) 
        {
            int total;
            return new Enumerable(delegate 
                {
                    return Membership.FindUsersByName(username, pageIndex, pageSize, out total).GetEnumerator();
                },
                delegate(object user)
                {
                    return User.FromName(((MembershipUser)user).UserName, false);
                });
        }
        protected IEnumerable findByEmail(int pageIndex, int pageSize, string userToMatch) 
        {
            int total;
            return new Enumerable(delegate 
                {
                    return Membership.FindUsersByEmail(userToMatch, pageIndex, pageSize, out total).GetEnumerator();
                },
                delegate(object user)
                {
                    return User.FromName(((MembershipUser)user).UserName, false);
                });
        }
    }
}
That's it! Simple enough, isn't it.
Thanks to Alex Shyba who helped me with some useful code!
After compiling the code and moving a dll to the /bin folder, don't forget to change a reference in web.config file to point it to a new UserProvider class.
<userManager defaultProvider="default" enabled="true">
<providers>
<clear />
<add name="default">
<x:attribute name="type">Sitecore.SharedSource.Security.Accounts.UserProvider, YOUR_DLL_HERE</x:attribute>
</add>
</providers>
</userManager>
<userManager defaultProvider="default" enabled="true">
<providers>
<clear />
<add name="default">
<x:attribute name="type">Sitecore.SharedSource.Security.Accounts.UserProvider, YOUR_DLL_HERE</x:attribute>
</add>
</providers>
</userManager>
For those who consider this so easy so that it's now worth to create a VS project I've built a ready-to-go Sitecore package with a dll and include file inside. Just install it and give it a try ;).
This is a Sitecore package.
Enjoy!
