I am looking for an instant messaging solution to facilitate communications between recovery vehicles in remote rural areas.

All the vehicles have internet connections, but they are intermittent depending on location.

Ideally we'd like something that has the following features:

Offline messaging: messages sent to clients who are offline will be delivered when they next come online, regardless of whether the sender is still online or not.

Lightweight: CPU cycles are limited on the machines in these vehicles. A bloated solution will be an issue. Client platform is primarily win32, but support for osx/linux/mobile devices would be a bonus.

Non-chatty: Bandwidth is a precious commodity for us, so services which use a minimal amount are ideal.

Fault tolerant: We see plenty of packetloss and high latency, so whatever we use needs to be able to function in trying network conditions.

I'm not fussed if we use a hosted platform like gtalk/skype/msn/icq/whatever, and likewise I can run a server if need be.

Suggestions would be appreciated!