A cloud-based identity and access management service for securing user authentication and resource access
Hello @Sokoban
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:> Problem to login https:// login.microsoftonline.com and you're getting error AADSTS700016 Application with identifier 'your_client_id' was not found in the directory 'XXXX XXXX XXXX'. This can happen if the application has not been installed by the administrator of the tenant or consented to by any user in the tenant. You may have sent your authentication request to the wrong tenant.
Solution:
You have solved this issue by Connect-MsGraph and Make a new appregistration
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.