Hi there! Here is the most common ways to resolve this issue. Since it is unclear exactly what is the root cause, I will list them all in order:
1) Go to Connections and reauthenticate the connection for the mailbox. If the connection is broken, it may appear as bad gateway.
2) If the connection is good, turn the flow off and turn back on after a couple of minutes to re-engage the flow and trigger.
3) (This one works often) Delete the trigger and re-add it. If the flow is fairly small, consider creating a brand new flow and just copy over the remaining actions into the flow. Regardless, the exercise here is to get a new trigger into the flow.
4) (This may also be root cause) make sure the mailbox you are attempting to connect to (if a sharedmailbox) has the correct permissions. Delegated access will not be enough. You need full permissions from the account in the connection string.
5) (Not a common path for me) try using the V2 trigger and see if it is a V3 trigger issue; although I have not had any issues with V3 trigger flows but worth trying if you are at this step.
6) Confirm this is not an exchange issue inside your tenant (check for service health status).
7) See #3 above, last resort is to rebuild the flow from scratch.
------------------------------------------------
⭐ If this was helpful, please like and check the box below "Does this answer your question" to help others find this too!
Always glad to help! 💯💯💯💯💯
Tom
Follow me on LinkedIn - Thomas Rice, PMP | LinkedIn