I like the idea of this thread! I myself am not a skilled code writer or graphic designer or anything but willing to help with the ideas.

Few has talked about SMS and GPS. Sending an SMS when SIM is beeing replaced (differs from the list provided) is a great idea. And it should send some information about the phone with it. For example the GPS coordinates, how much battery left, some sort of code with which you can set on the alarm by SMS like danx suggested (which is a great idea) etc.It could also send all of this into your e-mail if networks are available.

How about also some app that would send GPS coordinates into your e-mail, SMS or in some other place every hour or so? Of course if networks are available (e-mail). That way you could keep track where the phone is.

One interesting thing might be also a bit modified idea about the ringtone (or alarm) that would say "This phone is stolen, please call 'some contact number'!". So when someone is calling for the thief (ringtone), the thief is calling or doing some other thing which has been adjusted, it would trigger the phone to play that audiofile and lock the device. Only way to shut the audio would be typing a code. You couldn't even shut down the device without the code.

Of course everything related to encrypting your data, sending them into some secure place and deleting them would have been done right in the beginning.