Before there was widespread Internet available, there was something called UUCP (Unix to Unix CoPy) that was used to send email and files around the world. More info here: http://en.wikipedia.org/wiki/Uucp
It would be ludicrous to implement UUCP on the OLPC, however some of the ideas used in UUCP could be recycled. UUCP also worked between devices that spent most of their time UNCONNECTED. UUCP exploited networks of relays to get messages to their destination. UUCP networks piggybacked traffic on connections that other people paid for, for instance intercity tie-lines, to avoid long distance phone charges. In the same way, OLPC messaging could piggyback on motorcycle postal services already in place like Motoman.
It would be worthwhile to research the history of UUCP networks, the problems they encountered, and the techniques they used to solve them. Forewarned is forearmed.