Yes, this behavior makes sense. Generic functions are only compiled when they are monomorphized, i.e. when a use of them appears in the code that has all fully determined type parameters. How can it generate machine code if it doesn’t know the types, after all? 
When you used fn(), the functions in your provider crate were monomorphic, and thus codegen happened when that crate is compiled. After you changed it to FnMut(), monomorphization now occurs in the consumer crate instead.
To obtain the benefits of closed over state with the benefits of eager code-gen that you get from monomorphic functions, you can use &mut dyn FnMut(). You can even do this without changing your public signatures, by writing a secondary function:
pub fn do_the_thing<F: FnMut()>(mut function: F) {
_do_the_thing(&mut function);
}
// Monomorphized version for eager compilation
fn _do_the_thing(function: &mut dyn FnMut()) {
...
}
Also, this is not a question for internals, but rather https://users.rust-lang.org/