Hi,
The order status notification is sent when:
- the order status is being changed
- a "send notification" flag is activated
This "send notification" flag is activated either:
- when you manually change the status of an order in the backend and activate the "send notification to customer" checkbox
- when a payment plugin changes the status of an order and set that flag.
So basically, if it's not because you've changed the status manually with the notification checkbox checked, but it happened automatically during a payment notification to the payment plugin which changed the status of the order automatically, the issue comes from the payment plugin you're using.
Which payment plugin are you using ? I've never heard such issue with the payment plugins we developed ourselves so if it's a third party developer, I'm afraid you'll have to contact them for further help on that issue.