So send of GetObjectsWithID request (#5) with say... 100 objects. If any object does't exist you get a MsgFail (#1). However there is no (obvious) way of knowing which object it was. [Actually you can keep track of each response and what you sent and cross reference... not very elegant however - and a bitch to debug].
(In the case I got it from it seems that the object was deleted between getting a list of updated objects, and getting the response, due a turn regen in the middle).