I don't think tracking info APIs are particularly cheap at that scale. If the seller runs in high enough volume there is no need to check every single order to smell fraud.
I'm not so sure. I believe Amazon customers are getting a push notification on their mobile device for every delivery notification, which leads me to believe (at least in the case of Amazon) they have the data.