I think that the best option (in terms of power saving at least) would be to upload the device coordinates and other data whenever a new SIM card is inserted. An SMS to a pre-defined number could be possibly used too. In case GPS coordinates cannot be acquired the device could just keep on trying if the SIM isn't a known one.

The event could also be triggered by a remote SMS (like remote locking on S60 devices) in case the device is simply lost and not stolen.