This is at it's core an issue of variance. So first a variance primer:
About variance
Given a generic type Foo<T>, and two related types Animal and Dog extends Animal. There are four possible relationships between Foo<Animal> and Foo<Dog>:
- Covariance - The arrow of inheritance points in the same direction for 
Foo<Animal> and Foo<Dog> as it does for Animal and Dog, so Foo<Dog> is a sub type of Foo<Animal>, which also means Foo<Dog> is assignable to Foo<Animal> 
type CoVariant<T> = () => T
declare var coAnimal: CoVariant<Animal>
declare var coDog: CoVariant<Dog>
coDog = coAnimal; // 
coAnimal = coDog; // ✅
- Contravariance - The arrow of inheritance points in the opposite direction for 
Foo<Animal> and Foo<Dog> as it does for Animal and Dog, so Foo<Animal> is a actually sub type of Foo<Dog>, which also means Foo<Animal> is assignable to Foo<Dog> 
type ContraVariant<T> = (p: T) => void
declare var contraAnimal: ContraVariant<Animal>
declare var contraDog: ContraVariant<Dog>
contraDog = contraAnimal; // ✅
contraAnimal = contraDog; // 
- Invariance - Although 
Dog and Animal are related Foo<Animal> and Foo<Dog> have no relationship whatsoever between them, so neither is assignable to the other. 
type InVariant<T> = (p: T) => T
declare var inAnimal: InVariant<Animal>
declare var inDog: InVariant<Dog>
inDog = inAnimal; // 
inAnimal = inDog; // 
- Bivariance - If 
Dog and Animal are related, both Foo<Animal> is a subtype of Foo<Dog> and Foo<Animal> is a subtype of Foo<Dog> meaning either type is assignable to the other. In a stricter type system, this would be a pathological case, where T might not actually be used, but in typescript, methods parameter positions are considered bi-variant.  
class BiVariant<T> { m(p: T): void {} }
declare var biAnimal: BiVariant<Animal>
declare var biDog: BiVariant<Dog>
biDog = biAnimal; // ✅
biAnimal = biDog; // ✅
All Examples - Playground Link
So the question is how does the usage of T impact variance? In typescript the position of a type parameter determines variance, some examples : 
- Co-varaint - 
T is used in as a field or as the return type of a function 
- Contra-varaint - 
T is used as the parameter of a function signature under strictFunctionTypes 
- Invariant - 
T is used in both a covariant and contravariant position 
- Bi-variant - 
T is used as the parameter of a method definition under strictFunctionTypes, or as the parameter type of either method or function if strictFunctionTypes are off. 
The reasoning for the different behavior of method and function parameters in strictFunctionTypes is explained here:
The stricter checking applies to all function types, except those originating in method or constructor declarations. Methods are excluded specifically to ensure generic classes and interfaces (such as Array) continue to mostly relate covariantly. The impact of strictly checking methods would be a much bigger breaking change as a large number of generic types would become invariant (even so, we may continue to explore this stricter mode).
Back to the question
So lets see how, the usages of T impact the variance of Foo.
barCallback!: (val: T) => void; - used as a parameter in member that is a function -> contra variant position
 
baz(callback: ((val: T) => void)): void - used as a parameter in the callback parameter of another function. This is a bit tricky, spoiler alert, this will turn out to be covariant. Lets consider this simplified example: 
 
type FunctionWithCallback<T> = (cb: (a: T) => void) => void
// FunctionWithCallback<Dog> can be assigned to FunctionWithCallback<Animal>
let withDogCb: FunctionWithCallback<Dog> = cb=> cb(new Dog());
let aliasDogCbAsAnimalCb: FunctionWithCallback<Animal> = withDogCb; // ✅
aliasDogCbAsAnimalCb(a => a.animal) // the cb here is getting a dog at runtime, which is fine as it will only access animal members
let withAnimalCb: FunctionWithCallback<Animal> = cb => cb(new Animal());
// FunctionWithCallback<Animal> can NOT be assigned to FunctionWithCallback<Dog>
let aliasAnimalCbAsDogCb: FunctionWithCallback<Dog> = withAnimalCb; // 
aliasAnimalCbAsDogCb(d => d.dog) // the cb here is getting an animal at runtime, which is bad, since it is using `Dog` members
Playground Link
In the first example, the callback we pass to aliasDogCbAsAnimalCb expects to receive an Animal, so it only uses Animal members. The implementation withDogCb will create a Dog and pass it to the callback, but this is fine. The callback will work as expected using just the base class properties it expects are there.
In the second example, the callback we pass to aliasAnimalCbAsDogCb expects to receive a Dog, so it uses Dog members. But the implementation withAnimalCb will pass into the callback an instance of an animal. This can leas to runtime errors as the callback ends up using members that are not there. 
So given it is only safe to assign FunctionWithCallback<Dog> to FunctionWithCallback<Animal>, we arrive at the conclusion that such a usage of T determines covariance. 
Conclusion
So we have T used in both a covariant and a contravariant position in Foo, this means that Foo is invariant in T. This means that Foo<any[] | { [s: string]: any }> and Foo<any[]> are actually unrelated types as far as the type system is concerned. And while overloads are looser in their checks, they do expect the return type of the overload and the implementation to be related (Either the implementation return or the overloads return must be a subtype of the other, ex)
Why some changes make it work:
- Turning off 
strictFunctionTypes will make the barCallback site for T bivariant, so Foo will be covariant 
- Converting 
barCallback to a method, makes the site for T bivariant so Foo will be covariant 
- Removing 
barCallback will remove the contravariant usage and so Foo will be covariant 
- Removing 
baz will remove the covariant usage of T making Foo contravariant in T. 
Workarounds
You can keep strictFunctionTypes on and carve out an exception just for this one callback to keep it bivariant, by using a bivariant hack (explained here for a more narrow use case, but the same principle applies):
type BivariantCallback<C extends (... a: any[]) => any> = { bivarianceHack(...val: Parameters<C>): ReturnType<C> }["bivarianceHack"];
class Foo<T> {
    static manyFoo(): Foo<any[] | { [s: string]: any }>;
    static manyFoo(): Foo<any[]> {
        return ['stub'] as any;
    }
    barCallback!: BivariantCallback<(val: T) => void>;
    constructor() {
        // get synchronously from elsewhere
        (callback => {
            this.barCallback = callback;
        })((v: any) => {});
    }
    baz(callback: ((val: T) => void)): void {}
}
Playground Link