Before iOS 7 this was not possible or feasible since iTunes would restore an image of the OS that would be free from any locking. Now there is Activation Lock which neatly pre-empts any attempt to remove the Find My iPhone feature of iCloud. Effectively, with Find my iPhone, your device is effectively locked to your Apple ID.
For iOS 7 and later - enable Find My iPhone to prevent anyone else from erasing or using the device.
If my iOS 6 or less iPhone is stolen, can I remotely brick the thing, so resale value drops to zero?
No.
The best you can do is to wipe the data from the device with an app like Find My iPhone from Apple or the open source Prey application. The device will no longer contain your applications or personal data, but it will still function normally and the thief could then initialize it for their own use.
For apps like Apple's Find My Phone, how feasible is it for a thief to remove the apps?
Without wiping the device? Hard to impossible. And that's the whole point of these applications: to keep your data safe and the cost of losing the hardware. You're essentially cleaning it for them and getting it ready for their use or resale. But you're ensuring that they can't gain access to your personal data, your PayPal account, your bank accounts and anything else you might have your phone connected to.
In the UK, cell phone carriers will blacklist phones that are reported stolen so they can't be used on the network again. The bigger UK carriers do it. Not sure how common a practice it is in North America, or if carriers here are willing to do it all.
As soon as the device connects to the internet, Apple's servers will send the erase message to the phone. I have seen this happen three weeks after the message was sent and the effect was nearly immediate.
I don't know of any way to recall the erase message once you've sent it, and you should receive an email if the device ever registers and the erase message is sent.
All the things you did after the erase request are moot since if the phone never checks in, you can't really stop the erase and if it does ever check in, it will get erased and self remove from your list of devices.
You might open a support ticket with Apple to be sure the email will send if you erase the device (I haven't actually tested that sequence), but common sense says you might expect the email if the erase ever gets issued.
Best Answer
The backups do not get erased when you send an erase request to a phone. You are actually preserving the back ups in the sense that if your phone doesn't have a passcode lock or the passcode becomes compromised, whoever has your phone now could start deleting things and if the phone starts A new back up then your current backup would have less of your data on it.
The interface for deleting back up data of an iOS device is in the manage storage portion of iCloud. If you think someone has access to your iCloud account, change your password to prevent them from deleting the data.
So, unless other things happen, your back up data will be sitting in iCloud waiting for you to load it on your device if you recover it or on another device of your choosing.