To clarify, you are saying that your function returns any Fn(Message) -> bool, where the exact type is decided by user of a function, which is obviously not true - your function only returns a single possible function |_| true.
Instead, don't use generic type parameters. Function pointer will do, although it will prevent you from using closures (as each closure is its own unnameable type).
Perhaps @skysch can define QueryWriter as a trait and then have two separate impls, one where caller supplies the predicate and the other where no predicate is stored.
I'm not sure how that would work with From. It's probably not viable for the purpose of this thing anyway, which is to be a stateful wrapper around a Write implementor, so I'm perfectly happy storing the function pointer in the object.