C# interface static method not always resolving correctly to derived class

Yes, this is expected behavior. You have encountered a detail of C# known as Interface re-implementation. According to C# Specification §18.6.7 Interface re-implementation:

A class that inherits an interface implementation is permitted to re-implement the interface by including it in the base class list.

A re-implementation of an interface follows exactly the same interface mapping rules as an initial implementation of an interface. Thus, the inherited interface mapping has no effect whatsoever on the interface mapping established for the re-implementation of the interface.

Example: In the declarations

interface IControl
{
    void Paint();
}

class Control : IControl
{
    void IControl.Paint() {...}
}

class MyControl : Control, IControl // Here IControl is applied once again
{
    public void Paint() {}
}

the fact that Control maps IControl.Paint onto Control.IControl.Paint doesn’t affect the re-implementation in MyControl, which maps IControl.Paint onto MyControl.Paint.

The specification doesn't discuss static virtual members in interfaces, however the same principle applies. By explicitly including IFoo in the base class list of FooDerivedExplicit you have declared that you have re-implemented the interface and thereby established a new interface mapping for it. Absent the explicit inclusion of IFoo the base type's mapping is used for derived types.

Incidentally, there's nothing special about static members here. Hiding a base type instance member by applying public new to the derived type member that hides it will not override the base member, it will only re-implement the member and only when the interface has been reapplied. So if I modify your example as follows, removing all static modifiers:

internal class Program
{
    static void Main(string[] args)
    {
        new FooDerivedImplicit().Do();
        new FooDerivedExplicit().Do();
        GenericCall.Call(new FooDerivedImplicit());
        GenericCall.Call(new FooDerivedExplicit());
    }
}

public interface IFoo
{
    public virtual void Do() => Console.WriteLine("IFoo:Do");
}

public class FooBase : IFoo
{
    public void Do() => Console.WriteLine("FooBase:Do");
}

public class FooDerivedImplicit() : FooBase // Implicitly IFoo
{
    public new void Do() => Console.WriteLine("FooDerivedImplicit:Do");
}

public class FooDerivedExplicit() : FooBase, IFoo // Explicitly says is IFoo
{
    public new void Do() => Console.WriteLine("FooDerivedExplicit:Do");
}

public static class GenericCall
{
    public static void Call<TFoo>(TFoo foo) where TFoo : IFoo => foo.Do();
}

The output is the same, the public new void Do() of FooDerivedImplicit is not called when an instance of FooDerivedImplicit is passed into a generic method and constrained as IFoo.

Demo of static methods here and instance methods here.

This is expected behavior.

Unlike instance methods, there is no mechanism for static interface methods that are implemented up the class hierarchy (FooBase) to be overridden by derived classes (FooDerivedImplicit).

Consider the non-static case where what you want to do is possible without explicit reimplementation:

public interface IFoo {
    public virtual void Do()
    => Console.WriteLine("IFoo:Do");
}

public class FooBase : IFoo {
    public virtual void Do()
    => Console.WriteLine("FooBase:Do");
}

public class FooDerivedImplicit() : FooBase {
    public override void Do()
    => Console.WriteLine("FooDerivedImplicit:Do");
}

public static void Call<T>(T obj)
where T : IFoo => obj.Do();

here if we do:

var impl = new FooDerivedImplicit();
Call(impl);

we'd get FooDerivedImplicit:Do and not FooBase:Do.

This is because we can reuse the method slot in the method table of FooBase that's mapped to be the implementation for IFoo.Do by FooDerivedImplicit.Do. Detailed explanation of how it works

With static methods, however, there is no valid virtual modifier to use when we are implementing interfaces in classes, i.e. this won't compile:

public class FooBase : IFoo {
    public virtual static void Do()
    => Console.WriteLine("FooBase:Do");
}

so effectively static FooBase.Do is sealed and its descendants cannot reuse its method slot to provide their own implementation.

Derived classes can hide the method and provide a new implementation with new but this (as in the non-static case) is meaningless to the virtual dispatch that relies on a mapping between a specific method table slot and an interface method. This is is what you did that unfortunately can't work:

public class FooDerivedImplicit() : FooBase // Implicitly IFoo
{
    public static new void Do() 
    => Console.WriteLine("FooDerivedImplicit:Do");
}

On the other hand FooDerivedExplicit works

public class FooDerivedExplicit() : FooBase, IFoo // Explicitly says is IFoo
{
    public static new void Do()
    => Console.WriteLine("FooDerivedExplicit:Do");
}

because it says use the new method slot I explicitly declare and not the one that is inherited from FooBase when you do virtual dispatch for IFoo.Do.

So, reimplementing is the only way to provide derived class implementation for static interface methods which the base class also implements.

You can of course override static methods in an interface hierarchy:

public interface I {
    public virtual static void Foo()
        => Console.WriteLine("I");
}

public interface IBase : I {
    static void I.Foo() => Console.WriteLine("Base");
}

public interface IImplicit : IBase {
    static void I.Foo() => Console.WriteLine("Implicit");
}

public static void Foo<T>()
where T : I {
    T.Foo();
}

Then Foo<IImplicit>() will output "Implicit", and not "Base".