Even if the thief removes/replaces the SIM, the device still has a unique MAC.

I daresay you could construct a conservative state-machine that would be easy on the power.

Power on
Wait for a TCP/IP network interface (eg. eth0) to activate
Report location
While eth0 active, report location every hour.
Power off