Having a similar issue where the trigger “when a new email arrives in a shared mailbox (v2)" can take several minutes. If an email is moved from the inbox within a few minutes, the trigger misses the email and the flow doesn't run.
This is a public, government mailbox, and asking employees to wait 5 minutes or longer before processing messages in the inbox so the flow can run is not an ideal solution for serving the public interest.