The fulfillment API does not appear to be working correctly. It does state in the documentation that the fulfillment ID is currently the shipping number, but that is subject to change. Did that change and the documentation not get updated?
I'm actually using the href from the getOrders api which pre-populates the rest api call with the new order id (non legacy order ID) and the tracking / shipping number. The URL matches what the API expects, but its giving me an invalid fulfillment ID. I ran into this issue last weekend, and figured maybe the API was down or having maintenance, however, I ran again and I'm still getting the error.
The order number and shipping number are correct so I'm thinking something is either broken, or was changed.