Issues Creating Fulfillments and Fulfillment Events via Admin API

I’m working on an integration using the Admin API to create fulfillments and then update their status via fulfillment events.

The flow works perfectly in our test production store: https://mystore.myshopify.com. Here’s a summary:

  • Create Fulfillment:
    POST /admin/api/2025-04/fulfillments.json
    BODY:
    {
    “fulfillment”: {
    “message”: “The package was shipped this morning.”,
    “notify_customer”: false,
    “tracking_info”: {
    “number”: “1562678”,
    “url”: “https://www.my-shipping-company.com”,
    “company”: “my-shipping-company”
    },
    “line_items_by_fulfillment_order”: [
    {
    “fulfillment_order_id”: {fulfillment_order_id}
    }
    ]
    }
    }

*Add Fulfillment Event:
POST /admin/api/2024-07/orders/{order_id}/fulfillments/{fulfillment_id}/events.json`
BODY: { “event”: { “status”: “in_transit” } }

However, in two client stores using the exact same app and API scopes, the API does not create the fulfillment, 404 Not found responses. And even if I manually prepare the order in the Admin UI, trying to create a fulfillment event via API returns an empty response.
All permissions (scopes) of the app associated with the token are enabled, so we’ve ruled out a missing scope as the cause.

Is there anything specific that could cause this difference in behavior between stores?