When the devices disappear it's hard to know remotely whether they've had a physical issue or if they just stopped sending messages.
I propose a small tilt sensor (eg. http://oomlout.co.uk/products/tilt-switch) which opens/closes a contact when the device is moved. This can trigger a wakeup interrupt pin which will cause the device to send some SOS messages in its final few moments before it a) sinks b) goes out of range