Update: Daring Fireball pointed to this recommendation from Jesse Hollington: set a SIM PIN code, which will prevent your phone from registering with the cellular network after a reset or a SIM swap until/unless the PIN is entered. Be extremely careful, however, as the iPhone settings UI can be confusing and you may get locked out if the phone thinks you're entering an existing PIN incorrectly. Macworld now recommends a three-step deactivation process, including calling your carrier to make sure your phone SIM is turned off.
Update 2: Our colleague Michael Jones reports that there are situations where the 'stickiness' of location services can work in your favor: "My wife's iPhone 3GS was stolen in mid-September. By the time the iPhone 4S was released, there had been no sign of the 3GS and so we went ahead and replaced the phone, figuring that there would be no way to locate the old phone once it was deactivated. A couple of days before Thanksgiving, however, I received an email from Find My iPhone that the 3GS had been located, and briefly reported its location at a grocery store that does not have any open Wi-Fi networks in the area. A few days later, I received another alert as the thief had again turned the phone on at a different location, and the police were able to recover the phone."
A troubling issue with iMessages being sent to stolen iPhones has been reported by Ars Technica. According to the article, the issue was brought up by Ars reader David Hovis whose wife's iPhone was recently stolen. She replaced her phone, changed her Apple ID password and moved on.
While she was enjoying her new iPhone, the stolen handset was sold to an unsuspecting third-party who was using the phone on their wireless account. Incredibly, the stolen phone, which she deactivated with her carrier and remote wiped, was still sending and receiving iMessages on her behalf. She is only one example. If you search MacRumors or Apple's support forum, you will find several more examples.
Part of the problem may reside with Apple's authentication system for iMessage. According to a thread at Ask Different, Apple stores the device ID (UDID) and the Apple ID or mobile number for each device that uses iMessage. An iMessage is apparently sent to Apple's servers, which look at the destination email address or phone number of an incoming message. The server looks in its database for the UDID that's associated with the recipient's phone number or Apple ID. The server then uses this information to redirect the message to the correct phone.
It's possible, in the case above, that the UDID of a stolen phone remains in Apple's database and is not replaced by the UDID of the new phone. A message sent to the phone number of the person whose phone was stolen would go to the UDID of the stolen phone and not the new phone. The owner of the stolen phone can then respond back.
I've experienced a similar issue with FaceTime on the iPhone 4. I activated my phone and setup FaceTime on one phone number and then switched it to another phone number about a month later. The UDID remained attached to the original phone number and was not automatically updated by Apple. When I tried to make a FaceTime call, the recipient would see my old number. If they tried to FaceTime me with my new number, it wouldn't work. People could only contact me by FaceTime calling my old number. I was able to force Apple to update my UDID in its system by resetting my phone using iTunes according to Apple's instructions.
The iMessage issue appears to be similar to the FaceTime issue noted above, but it's not identical. While FaceTime can be corrected by erasing your phone, the iMessages issue is not corrected by a similar remote wipe procedure. I'm not sure why a remote wipe wouldn't fix the iMessage issue; maybe there's a difference between a remote wipe and an iTunes reset or Apple's servers are configured slightly different for the two services. Regardless, the iMessage issue is a serious one that Apple hopefully will address.