The issue looks to be that the eBay API is sending back the 'Order Number' (what we as a seller see against the sales record on eBay Seller Hub) for these particular orders, rather than the 'Order ID' (eBay's internal ID for the order). For example;
Order Number = XX-XXXXX-XXXXX
Order ID = XXXXXXXXXXXX-XXXXXXXXXXXXX
This is causing the eBay API to then report '21916340 - Sale record doesnt exist' when we use the Order Number to reference the order, rather than the Order ID.
This is surely an internal bug with the API, but there's no way of reporting this to eBay unless I pay for support hours...