The triggers on SharePoint lists (e.g. "When item is updated") stop working when the list contains more than 5000 items. In the immediate term, there should be a clear warning about this fact in the description.
But this is a blocker to using Flow with any SharePoint list of significance, and always a risk. Please make these triggers work reliably regardless of list size.
Perhaps this can be avoided by implementing the triggers through webhooks rather than queries: