The "Using fallback deterministic coder for type X" warning means the type hint

.with_output_types((Tuple[MessageKey, Message]))

is being lost somewhere.

I reproduced this and found that the type hint is not properly propagated in https://github.com/apache/beam/blob/9612583296abc9004f4d5897d3a71fc2a9f052bb/sdks/python/apache_beam/transforms/combiners.py#L962.

This should be fixed in an upcoming release, thanks for reporting the issue.

In the meantime you can still use this transform even with the "Using fallback deterministic coder for type X" warning, it just wont use the custom coder you defined.