We ended up removing the abovementioned `bulkUpdatePriceQuantity`, because this internally causes eBay to call the Trading API (you know, the one which is limited to 1500 calls a day), one call for each product. So that was not good. After a while, we noticed that it "just worked" without it. Could be a bugfix on the eBay side of things, or simply luck that we didn't encounter the bug again.
We had the same issue after merging over to the Sell API and bulk uploading everything. Turns out, some offers were just corrupt in some way. They had inventory, but would show up as out of stock and unable to be purchased. Deleting the inventory for those items, then going back and creating the inventory/offer fixed the issue.