Can thieves get around Apple's "Find My Phone" feature?

Can thieves get around Apple's "Find My Phone" feature? I had my iPhone 4S stolen and had "Find My Phone" turned on. What happens if they reset my phone or install a custom rom? How easy is it to get away from this feature?

Very easy. Find My iPhone is not a deterrent to anybody who steals your iPhone who has any real knowledge of iOS. Just a few examples of ways in which the feature can be effectively compromised:

• If you haven't protected your iPhone with a passcode, the thief can simply go in and turn if off under your iCloud settings as easily as you could.
• The feature only operates at the OS level. It will still be active after simplyrebooting the iPhone, but if the iPhone is completely erased and returned to factory settings, the Find My iPhone feature goes away with it. Note, however, that if you've password protected your iPhone it will be difficult fo a thief to erase your device until they can connect it to a computer running iTunes and perform a "Restore" operation. This also applies if you do a remote wipe of your iPhone, of course, which is effectively the same thing.
• The feature relies on a data connection. Taking out your SIM card and being away from any pre-configured Wi-Fi hotspot (e.g. one that you had already setup your iPhone to access before it was stolen) will render the feature ineffective. This also makes the feature considerably less effective on an iPod touch or a Wi-Fi only iPad.
• Obviously as well if the iPhone is turned OFF the feature will not work.
• If you've set a PIN on your SIM card, your iPhone will lose access to the cellular network as soon as it's rebooted. The SIM PIN is a good security feature that -- when combined with a properly-configured passcode -- will prevent a thief from using your cellular account to rack up a large bill for you, but by the same logic it will prevent your iPhone itself from using your cellular account until the PIN is entered.
• Likewise, if you call your cellular carrier and cancel your service -- usually a good idea after any phone has been stolen -- your iPhone will no longer be able to access the cellular data network, and "Find my iPhone" then becomes about as effective as it would be on an iPod touch, requiring a Wi-Fi network in order to connect to Apple's servers and report its location.

These last two points mean that a clever thief could take your iPhone and immediately turn it off or remove the SIM card until they can get it to a computer to erase it. Once it's erased all bets are off -- it's effectively not "your" iPhone anymore as far as iOS is concerned.

Note that all of the same restrictions apply to the Remote Wipe feature as well. If Apple's servers can't communicate with the iPhone, if "Find My iPhone" has been switched off manually or if the device has already been wiped, then "Remote Wipe" (and remotely setting a lock code) won't work either.

One positive note is that all of the remote operations (find, wipe, lock) are queued by Apple's servers, so even if your iPhone is unreachable when you initially try, they will be processed when (or if) the device comes back online -- the remote wipe/lock will simply be performed at the first opportunity, while a find request can send you an e-mail once the iPhone is located and the web page will display the last known location.

iOS 6 now includes a new "Lost Mode" that provides the additional ability to trackthe location of your device once it's been flagged as "lost." Previously, you could receive a notification once the device had popped up somewhere, but that would only show the location at that particular point in time. With iOS 6, once "Lost Mode" has been engaged, the system begins actively tracking the device, which will allow you to see a history of all of the places where the device has appeared and moved to since "Lost Mode" was first engaged.

Update (2012-11-16): Added information on SIM PINs and active cellular accounts and how this affects the process, as well as "Lost Mode" on iOS 6.