Need help generating expression tree for multiple search strings across multiple properties

If I'm reading your question right, I don't think you need to use an expression tree.

You can use reflection to inspect the properties of the instances in the _MyDataOfAnyType and use that to get the string value of any properties that return a string. Then, check the searchString if it .Contains the returned value of the property. And by extending that method to have a set of comparators capable of comparing all the different type-sets that makes sense in your application neither the properties nor the search criteria has to be string values.

This example shows what I mean;

using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    public abstract class SearchComparator
    {
        public abstract bool IsApplicable(object searchValue, object actualValue);
        public abstract bool IsMatch(object searchValue, object actualValue);
    }

    public abstract class ComparatorBase<T1, T2> : SearchComparator
    {
        protected abstract bool IsMatch(T1 searchValue, T2 actualValue);
        
        public override bool IsApplicable(object searchValue, object actualValue)
        {
            return searchValue is T1 && actualValue is T2;
        }

        public override bool IsMatch(object searchValue, object actualValue)
        {
            return IsMatch((T1)searchValue, (T2)actualValue);
        }
    }


    public class StringToPartialString : ComparatorBase<string, string>
    {
        protected override bool IsMatch(string searchValue, string actualValue)
        {
            return actualValue.Contains(searchValue);
        }
    }

    public class StringToPartialDecimal : ComparatorBase<string, decimal>
    {
        protected override bool IsMatch(string searchValue, decimal actualValue)
        {
            return actualValue.ToString().Contains(searchValue);
        }
    }

    public class DecimalToDecimal : ComparatorBase<decimal, decimal>
    {
        protected override bool IsMatch(decimal searchValue, decimal actualValue)
        {
            return searchValue == actualValue;
        }
    }

    public class ClassA
    {
        public string PropertyA { get; set; }
        public bool PropertyB { get; set; }
        public int PropertyC { get; set; }
        public string PropertyD { get; set; }
    }

    public class ClassB
    {
        public bool PropertyA { get; set; }
        public decimal PropertyB { get; set; }
        public string PropertyC { get; set; }
        public string PropertyD { get; set; }
    }

    public class Program
    {

        static IEnumerable<object> GetProperties(object target)
        {
            IList<object> values = new List<object>();
            foreach(var property in target.GetType().GetProperties())
            {
                // Try-Catch here in case the getter chucks an exception
                try {
                    var value = property.GetValue(target);
                    values.Add(property.GetValue(target));
                }
                catch {
                }
            }
            return values;
        }


        static IEnumerable<object> Search(IEnumerable<object> dataOfAnyType, IEnumerable<SearchComparator> comparators, IEnumerable<object> searchCriterion)
        {
            ISet<object> matches = new HashSet<object>();

            foreach(var data in dataOfAnyType)
            {
                foreach(var propertyValue in GetProperties(data))
                {
                    if (propertyValue != null)
                        System.Diagnostics.Debug.WriteLine("Looging for {0}", propertyValue.GetType().FullName);
                    foreach(var criteria in searchCriterion)
                    {
                        foreach(var comparator in comparators.Where(comp => comp.IsApplicable(criteria, propertyValue)))
                        {
                            if (comparator.IsMatch(criteria, propertyValue))
                                matches.Add(data);
                        }
                    }
                }
            }

            return matches;
        }

        static void Main(string[] args)
        {
            // This holds one instance for each type-pair that your application can compare
            var comparators = new SearchComparator[] {
                new StringToPartialString(),
                new StringToPartialDecimal(),
                new DecimalToDecimal()
            };

            var searchCriterion = new List<object> {
                123.2312m,
            };

            var _MyDataOfAnyType = new object[] {
                new ClassA { PropertyA = "Hello", PropertyD = "no data"},
                new ClassA(),
                new ClassB { PropertyC = "123" },
                new ClassB { PropertyB = 123.2312m },
                new ClassB { PropertyA = true, PropertyD = "World!"}
            };

            var matches = Search(_MyDataOfAnyType, comparators, searchCriterion);

            var foundAny = matches.Any();

            Console.WriteLine("Found {0} matching objects!", matches.Count());

        }
    }
}

Hope this helps,
Fredrik