I am sure this might be possible (not applicable to removable battery phones) but there would be an app or something which would prevent the phone from being shutoff without a passcode ?
Although mine is no fool proof but i have an iPhone and it is jailbroken and as a first preventive measure i have a passcode setup. I have this app installed from cydia which will take the picture from front camera when wrong passcode is entered, start the EDGE/3G on my phone (if not already on) and email to picture to a predefined email address. The EDGE/3G then stays on and it cannot be turned off for a certain period of time (not sure how much).
Also when someone tries to turn off the phone in locked mode, the app does not allow the phone to be turned off and every power off attempt will mean more pictures captured and emailed. Now since there is no way the person can turn off internet without unlocking the phone, it may aid in tracking.
But as with all methods, if the SIM card is removed all this fails.
But yes it does have feature to send a SMS when a new non approved SIM card is entered and what i can do after that is that i can send remote commands as SMS to this new number (custom setup) and these commands will perform the actions which they have been told to (you defined this before only).
Like say i send a SMS as "locat10n' i will receive a SMS with the GPS co-ordinates of the phone.
Similarly if i send SMS as "takep1c' then it turns on EDGE/3G and emails me pic.
The good part is that even if the new SIM does not have internet plan and does have some balance the internet will work consuming his main balance.
I have deliberately choosen words with numbers above as the app is too sensitive that even if the word is there in any SMS that comes it performs the commands and before i had setup as "location" and when i had SMSed someone with text as "what is your location" the app interpreted it as command and i started receiving bulk emails with location every 10 minutes.