What you can't do
- You can't stop your AT&T monthly bill. You're under contract.
- You may or may not be able to cancel Apple Care and perhaps get a prorated refund (up to Apple)
- You can't get AT&T or Apple to disable the stolen phone, you can't prevent it from being resold.
- You can't buy a refurbished iPhone from AT&T without a new contract. I don't think you can buy one from Apple at all.
Initial stepsYou must choose between
- going to AT&T and suspend wireless service, AT&T will treat phone as lost or stolen.
- Leaving service in place and using Find My iPhone to track the phone. If the phone is locked the thief probably can't make a call.
- Wiping the phone remotely from Find My iPhone.
Get a temporary phone and ask AT&T about optionsIf you don't have a GSM dumbphone in the closet a neighbor does. Bring it an AT&T store and they'll pop in a SIM card. They'll also let you know your options
- Early termination fee to end contract: for us $325 less $10/month of service or $285. This has risen sharply over the past years, older contract costs may be much less.
- Cost for a phone with a contract extension: for us $250 plus the contract cost of the phone ($0 for 8GB 3GS, $200 for 16GB 4S). This cost falls the further into your contract you are.
Consider your iPhone choicesA few months ago I predicted a growing supply ("glut") of used iPhones on the market as a result of carrier-locking and SMS pricing. I'm not seeing that in today's used iPhone market. For example, very few if any businesses sell used iPhones online. (Amazon has some listings, but they're strange. For example, they frequently don't specify carrier lock status.) On the other hand, many business happily buy iPhones, paying $150 for semi-working 3GS! As best I can tell there are several things going on:
- There's still robust demand for unlocked iPhones overseas, and 3GS iPhones are easy to unlock.
- Because of the cost of out-of-contract iPhones and their fragility  (esp. to water) there's a flourishing market in iPhone repair -- and thus for iPhone parts.
- There are lot of stolen iPhones but they seem to cycle into the overseas and parts market even more than into the (riskier) resale market.
- 16 GB 3GS from either eBay or Craigslist: $200-$220 but significant risk of stolen or defective device.
- 16 GB 3GS from World of Wireless: not known, but if anyone has used devices for sale they might. Presumably higher price, but may have redress
- 16 GB 4S from Apple, unlocked: $650. A reader (Martin) points out that a full-price device is a much better fit to insurance policies (credit card or other) than a subsidized device. It's treated like an insured laptop. If you can find a compatible service contract priced for subsidy-free phones and insurance coverage this is a very best option for a replacement or initial phone.
- 8 GB 3GS from AT&T (new) with contract extension: $250 + $36 "upgrade fee" 
- 16GB 4S from AT&T (new) with contract extension: $450 + $36 "upgrade fee"
- 16GB 4S from AT&T (new with a new contract for me: $200 + $36 "upgrade fee" (but then I have to put off getting my iPhone 5! .
Subsequently I met with a more senior AT&T retail rep. In this case I mentioned (see below) that I was planning to buy out my son's contract; that might have inspired him but he struck me as a natural sales and retail guy. He added another option and some additional information:
- Even though every new subsidized phone comes with a $36 service fee (smaller percentage of a $200 4S than of a 0$ 3GS), he can provide heavily discounted accessories (case?) to offset the fee.
- As the primary line on a multi-iPhone family plan I can get an 'upgrade' more often than I realize. I thought I was eligible every 18 months, he said every year was more likely.
- We could start up a new family line contract ($10/month + tax/fee, no data). There's a loophole by which he can get a subsidized iPhone on the new family line (no data) but activate it on my son's like (data). That would be cost competitive with extending his contract, but it would provide us an extra PlainPhone SIM and wouldn't extend his contract.
Consider your Network choicesThis is where things get interesting. A few weeks ago I put an H2O Wireless voice and SMS only SIM into my youngest son's iPhone. He gets voice and SMS service for a total of about $90 (incl fees, taxes) over two years. That's compared to about about $770 (incl. fees, taxes) for my older son's contracted service. That's a rather big difference, especially since ...
- Neither talks on the phone
- They can use iMessage when on home Wifi (often)
- They mostly text, and texting is costly on AT&T but cheap on H2O
- I'd just as soon they not have data access outside the home, especially given the iPhone's fake parental controls. Those "colorful" YouTube videos can chew through a 200MB data plan pretty quickly. The only advantage of the data plan is Find My iPhone (not that helpful) and iMessage (but H2O texting is relatively cheap).
What we're doingI'll think this over for a bit while my son uses an old PlainPhone. Reviewing the spreadsheet however, the H2O wireless (wifi data only) option looks very competitive over a two year cost cycle. If I take that route I'll either
- buy a used 16GB 3GS (World of Wireless?)
- get a 16GB 4S on my contract and defer my iPhone 5 (or, since my son will be up for a new contract now, get an iPhone 5 with a 2 yr contract on him in Nov/Dec).
- buy him an iPod Touch and leave him with the PlainPhone.
 AMEX users may have some coverage of a lost iPhone, but not much. In this case the lost phone wasn't the one we got on contract.
 For about $200 Apple will repair just about any iPhone damage - at least for an in-contract phone. I don't know what the charge is for older iPhones, but it wouldn't surprise me if it was still $200 (plus tax).
 My wife's is phone eligible in May 2013, earlier if we pay a bit. So my iPhone 5 delay might be only a few months. This is one of the better options if we stayed with AT&T.
 In another sign of AT&T's desperation, they recently doubled their "upgrade fee" from $18 to $36. You can't avoid this fee by purchasing through Apple. If you are a valued customer AT&T will often provide some kind of credit or offset -- just ask before you pay.
In the end I traded a bike we wanted to sell for a friend's 3GS and we'll make the H2O transition and AT&T contract buy out at another time.
Since this post the carriers have announced a national registry for stolen devices. I'll enter our stolen phone into that registry when it comes out.
Also, I was reading about MAC addresses recently and wondered about recovering an iPhone by scanning for use of its MAC addresss. In Oct 2010 Steven Brannigan did that using an app called Ap-Finder to locate a device over WiFi --though the technique relied on knowing roughly where the phone was.
Lastly, if you save a screenshot of your iOS device's Settings:About screen (takes two shots) you can get the "Wi-Fi Address" (MAC address), Bluetooth, IMIE,and Serial Number. Note the SIM card stores the IMSI, so the SIM (subscriber identity module) card ties an IMIE to a Subscriber. I believe the ICCID identifies the SIM card. So in database jargon the "join" row is:
- ICCID (SIM card) | IMIE and/or MAC (device) | Phone number | Subscriber account