The easy answer to the "islanding" problem would be for a message to only be sent onwards if the ID of the receiver was unique. If the message was passed back, then both phones would be told that the message hadn't got throguh yet, and would then continue trying to send the message to others that were new. This would further increase the odds of one of the phones getting through. Of course, it increases bandwidth a little and processing and storage overheads by an amount.

Might be tricky getting the ringback to say the message has been delivered, but normally it wouldn't be a problem, only in certain circumstances.