I didn't see an explanation for an alternative solution. I've been trying to think of one all morning and can't!

Maybe he just means all friends whether they are logged in or not?

no, they're not sending notifications at every event. As far as I can tell, they're using an asynchronous algorithm that lazily propagates events and provides no responsiveness guarantees. (sort of ultra mushy stretchy unreal time guaranteed)

Sorry, but how is that different to sending all notification events to all users? You are still sending all notification events to all users, whether you do it lazily or not!

I guess they meant they don't send a notification per message, but rather batch them somehow.

exactly! This leads to people having inconsistent (with reality) information about the availability of other people who have just logged on or off!