You should be starting an activity to trigger the automation when a new mail arrives. Since activities are queued, only one can execute at a time. This is what I would do.

The other option is to use the Lock component. When a new mail arrives, you can request a lock. When it returns True, you can trigger your automation. Once it completes, you would release the lock. When another request comes in while a lock has already been requested, it will get held at the RequestLock method until either the lock is released or until the timeout has been reached (I believe the timeout is in minutes or seconds instead of milliseconds). I would not use this component for this purpose though. I would use an activity.

You do not need the interaction. You could simply start an activity without a key. Since you are using the NewMail event to trigger the activity, there is really no waiting. On startup, you might check your Inbox to see if any arrived while you were offline, but otherwise, your flow is correct.

Are you getting two NewMail events?