WC “Order Complete” Email not sent

Due to some issues with an external shipping management tool (Veeqo), I am debugging a website where the “Order Complete” email is never sent. Please see below the exact behaviour and debug done.

1. If I trigger the “Order Complete” in the backend, manually, the email is sent
2. If I add a hook as below shown to theme or plugin, to trigger the email when the order goes to complete, the email is never sent
3. Similarly, if an external Tool like Veeqo sets the Order to complete, the email is never sent.

Technically, if I add this to theme or plugin:

function trigger_email_on_complete_status( $order_id, $old_status, $new_status ) {

		// Check if the new status is 'completed'
		if ( 'completed' == $new_status ) {
			// Get the order object
			$order = wc_get_order( $order_id );
			// Ensure we have an order instance
			if ( $order ) {
				// Get the email instance related to completed orders
				$mail = WC()->mailer()->emails['WC_Email_Customer_Completed_Order'];
				$mail->trigger( $order_id );
			}
		}
	}
add_action( 'woocommerce_order_status_changed', 'trigger_email_on_complete_status', 10, 3 );

… then the email should fire whenever the order goes to complete.
And indeed, if I debug log the single Variables in that function I can see that:
– the email is enabled
– the recipient is set
– the order status is correct (complete)
– the mailer is instantiated

…. yet, the email is NOT SENT by this code.
I know this because:
– when I trigger the “order complete” in the backend, and use above code, the email should be sent _twice_. But it is not, it is sent only _once_.
– if any non-wp-admin related action (Veeqo, own custom code, etc) trigger the order complete, the email is not sent at all.

Yet in all cases, the above function does get triggered, the mail data is instantiated, as I can see in the debug log… it just seems that send() of the WP_Mail class is never sending the mail.

Note that ALL other emails (order received, etc) ARE sent just fine, in all cases, be it triggered manually or externally by Veeqo or via code.

It is only this one email (WC_Email_Customer_Completed_Order) that is not sent.

I am turning a bit in circles here, it is unclear why it does not work, and how to fix this.
Of course, I already tried the basic things like testing with themes that are not modified, no plugins, and confirmed the issue happens in several different scenarios, no only when Veeqo is used.