Hi,
i'am facing the same problem and after some debug i figured that the findMatchingRedirect($source_path, array $query = [], $language = Language::LANGCODE_NOT_SPECIFIED) method doesn't able to get the right hash from database in some cases.
The source_path passing to the method is a /node/nid but in database the redirect_source__path is an alias without langcode.
The language used to generate array of hashes to query database is the current of the redirect_source__path or und but never the other so an "en" source to a "fr" destination can't work.
And The Url object use to the redirection once the right redirection is found is from the original request and not from redirection.
Maybe i'am wrong but for me the language of the redirection is the language of the destination but it seem to be these of the origin.
No time to investigate more but there is a dirty quick test patch which seem to fix it in my tests cases