It seems to me that the two services are not the same thing.

If taxNumber, name, whatNot produce a unique id, then you can join em all together, use that as your orderId and have the same GetOrder(taxNumber, name, whatNot) locally as the service.

If they do not, then the external service and your local repository are not implementing the same interface. One gets a unique record and one searches for matches.

You shouldn’t attempt to join the two, because even if you manage it with some clever code the Business logic isn’t the same. Have:

Interface IOrderSearcher
  +GetOrder(taxNumber, name, whatNot) : Order

Interface IOrderRepository
  +GetOrder(orderId) : Order

Your local repository can implement both if required.

There is nothing wrong with approach number 2, and in fact this is the approach I’ve seen the most. Approach #1 could work as long as you lean on encapsulation to limit how clients can use this “order entity finder object”:

public class OrderIdentifier
{
    public int OrderId { get; private set; }
    public string TaxNumber { get; private set; }
    public string Name { get; private set; }
    public string WhatNot { get; private set; }

    public OrderLookupMethod LookupMethod
    {
        get => OrderId > 0 ? OrderLookupMethod.ById : OrderLookupMethod.ByTaxInfo;
    }

    public OrderIdentifier(int orderId)
    {
        OrderId = orderId;
    }

    public OrderIdentifier(string taxNumber, string name, string whatNot)
    {
        // ...
    }
}

public enum OrderLookupMethod
{
    ById = 0,
    ByTaxInfo = 1
}

And then in your repository:

public Order GetOrder(OrderIdentifier id)
{
    Order order = null;

    switch (id.LookupMethod)
    {
        case OrderLookupMethod.ById:
            order = // Find by Id
        case OrderLookupMethod.ByTaxInfo:
            order = // Find by tax info
        default:
            throw new ArgumentException(...);
    }

    return order;
}

The combination of the two constructors and making the setters private for the OrderIdentifier class ensures clients instantiate this correctly:

OrderIdentifier byId = new OrderIdentifier(4); // Find by Id
OrderIdentifier byTaxInfo = new OrderIdentifier(taxNumber, name, whatNot); // Find by tax info

If you’re looking for the simplest solution from your current point, the “two methods and a conditional” option works just fine.

If you’re looking for a more elegant, polymorphic solution, without passing redundant parameters, then here are a couple of approaches you could consider.

What you really have is two different implementations of an IOrderQuery interface (or whatever you prefer to call it). The trouble is that those implementations need different constructor parameters, supplied at request time and your composition is done in your application’s root.

You can solve that problem with a factory.

public class InternalOrderQuery : IOrderQuery {
    public InternalOrderQuery(string orderId) { ... }

    public Order Get() { // fetch order by ID }
}

public class ExternalOrderQuery : IOrderQuery {
    public ExternalOrderQuery(string taxNumber, string name, ...) { ... }

    public Order Get() { // fetch order by things }
}

public interface IOrderQuery {
   Order Get();
}

public class OrderQueryFactory {
    public IOrderQuery Create(RequestData stuff) { ... }
}

Inject the factory and, in Create, create the order query as appropriate – the rest of your code doesn’t know the difference.

Alternatively, your first approach works well but can benefit from better encapsulation:

public class OrderRequest {

    private String name;
    private String taxNumber;
    private String orderId;

    public OrderRequest( ... ) { // assign fields }

    public Order Execute(IOrderRequestContext context) {
        return context.Get(name, taxNumber, orderId);
    }
}

Implement IOrderRequestContext twice – once to execute against the remote DB and once against the local.

You could take this further and make the request parameters key/value pairs – that way the context can just read what it needs without needing you to explicitly define every possible parameter for every possible implementation.