Exposing WCF Service with dynamic search operation

Without knowing its intended audience (Intranet / Internet), I'm assuming Intranet.

In my opinion, you are giving a lot of flexibility to this service in one method call, which isn't immediately clear how a user would structure a call to this. The caller has to have knowledge of a "propertyId" which doesn't make too much sense on a glance. I hope your API documentation describes this well, and how the user would retrieve what these IDs are.

So here is my assumption of the coded interface:

public interface ISearchService
{
    List<object> Search(string clientId, IEnumerable<PropertyQuery> propertyQueries);
}

// Element
public class PropertyQuery
{
   // Attribute
   public string PropertyID { get; set; }

   // Array
   public IEnumerable<Value> Values { get; set; }

   // Attribute
   public byte AND { get; set; }

   // Attribute
   public byte OR { get; set; }

   // Element
   public string Operator { get; set; }
}

// Element
public class Value
{
   // Attribute
   public int Id { get; set; }

   // Attribute
   public byte Start { get; set; }

   // Attribute
   public byte End { get; set; }

   // Text
   public string Text { get; set; }
}

To make this a little simpler, I would add a single class that takes all parameters and a class returning the results, following the Request/Response pattern. This means that the interface can change over time, and should not affect backwards compatibility.

public interface ISearchService
{
   // Gets the search criteria for the screen
   SearchCriteriaResponse GetSearchCriterias(SearchCriteriaRequest request);

   // Searches by the search criteria
   SearchResponse SearchBy(SearchRequest searchCriteria);
}

// Base elements for a response
public abstract class ResponseBase
{
   public bool Success { get; set; }
   public string Message { get ; set; }
}

public class SearchCriteriaResponse : ResponseBase
{
   public string[] DocumentTypes { get; set; }
   public string[] BankName { get; set; }
}

public class SearchResponse : ResponseBase
{
   public IEnumerable<SearchResult> Results { get; set; }
}

public class SearchRequest
{
   public string ClientId { get; set; }
   public string[] BankNamesToMatchExactly { get; set; }
   public string[] BankNamesToPartiallyExactly { get; set; }
   public string[] DocumentTypesToMatchExactly { get; set; }
   public string[] DocumentTypesToPartiallyExactly { get; set; }
   public DateTime? StartDate { get; set; }
   public DateTime? EndDate { get;set; }
   public bool CheckBetweenDates { get; set; }
}

This interface is a more clean on its approach. Its slightly larger, but it makes the ORing and ANDing much more obvious. It also makes the code cleaner at the service side as each of these properties have well-named properties and should be easy to implement:

public List<SearchResponse> SearchBy(SearchRequest searchCriteria)
{
   IQueryable dbQuery = DbContext.BankNames;

   foreach(var bankName in searchCriteria.BankNamesToMatchExactly)
   {
      dbQuery = dbQuery.Where(bn => bn.BankName == bankName);
   }

   foreach(var bankName in searchCriteria.BankNamesToMatchPartially)
   {
      dbQuery = dbQuery.Where(bn => bn.BankName.Contains(bankName);
   }

   // etc..
}