Hello @Randolph Cheng,
I'm glad that you were able to resolve your issue and thank you for posting your solution so that others experiencing the same thing can easily reference this! Since the Microsoft Q&A community has a policy that "The question author cannot accept their own answer. They can only accept answers by others ", I'll repost your solution in case you'd like to "Accept " the answer.
Issue: User's password is managed on-premises. But no on-premise server exist.
Solution: As you are not managing Microsoft Entra Connect anymore in your tenant, MS support engineer recommended to disable the sync. After disabling sync fix got fixed. Below are the commands given to disable sync.
install-module msonline
connect-msolservice
Set-MsolDirSyncEnabled -EnableDirsync $false
If you have any other questions or are still running into more issues, please let me know. Thank you again for your time and patience throughout this issue.
Please remember to "Accept Answer" if any answer/reply helped, so that others in the community facing similar issues can easily find the solution.
Thanks,
Raja Pothuraju.