I think there is one way to really solve the issue in question. As I understand it, the problem is that when user logs it, he doesn't know whether the contact is online or not. Sending all presences together is not an option, as it would require waiting for all the probes to respond.
Now, I'm not exactly sure how this works with server implementations, but my guess is that the once the s2s connection is established (which can vary widely for every server) all the probes (should) get processed and returned in a relatively short timespan. What we need to do, is to make client aware that he has received all the delayed presences from a particular domain. It would then be possible to display contacts with some sort of "waiting" state, so the user knows whether the contact in question is offline, or the s2s connection just didn't get through yet. All in all, this could be very simply defined in a short XEP.
