I have encountered the same exact error in the same situation - Power Automate flow using an AI Model. This has been working without issue for a year and then this morning it fails repeatedly with the error:
Could not load type 'Microsoft.Xrm.Kernel.Contracts.Internal.ICrmServiceCollectionFactory' from assembly 'Microsoft.Xrm.Kernel.Contracts.Internal, Version=9.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35'.
I have an entire supply chain department that is having to process hundreds of documents manually this morning because of this. They don't have the luxury of waiting for someone at Microsoft to admit they changed something and fix it.