In older TYPO3 versions (<9.5) the fe_user passwords in MD5 where converted live when logging in by the extension salted_passwords.
Now I still have some fe_user passwords in MD5 but the salted_password extension does not exist anymore. When an fe_user tries to login with md5 I get the error:
No implementation found to handle given hash. This happens if the stored hash uses a mechanism not supported by current server. Follow the wiki link to fix this issue.
In the earlier version of TYPO3 8.x (AFAIK, In TYPO3 9.x scheduler task no longer exist because it uses different algos!), you will have the option to convert user passwords to salted hashes.
Did you missed that?
Scheduler
module in the System
Convert user passwords to salted hashes
You got to go!!