The kicker will be when they can do this, even when we've flipped the off switch. For now, there's always the off switch.
Note that location services comprises many different technologies, not all of which can be turned off. Many of them are required for the phone to operate. The upcoming FCC regs, for instance, require 100m self-locating ability to always be on. I guess for things like 911 service?
Speaking of paranoia, there's also rumors that the FBI/black helicopter/MIB bunch can actually power-up your phone remotely, especially with some models. This sounds completely out-of-left-field to me, but who knows? Court docs show they can use your phone as a listening device even when you're not calling somebody, so I wouldn't put other things along these lines past them. There's probably a good reason Osama Bin Laden refused to have anybody associated with him possess a cell phone, whether it was used, had a battery in it, or not. Seems like I read something somewhere once about illuminating electronics gear with microwaves, then reading the signature of the radiation emitted. But it could have been in a pulp sci-fi novel. As I said, it's difficult to tell where reality ends and paranoia begins with this because reality is quickly catching up to the paranoia of just a few years ago. Who would have imagined sub-meter resolution on where you are? That's almost accurate enough to tell if you're wearing the phone in your jacket pocket or on your belt. Crazy stuff.
I do remember reading about locally fingerprinting an Off phone based on its passive radio response, and this seems feasible.
When the phone is On, total location privacy is out the window, as Ma Bell always knows what towers you're near and can triangulate. Everything else you've said can be (and probably is) implemented in invisible layers of software.
End-to-end privacy would be a nice step forward, but assuring this requires an auditable interface between the radio transceiver and the computer/sensors. Any fix for the location problem involves decoupling identity/billing from the physical infrastructure.
Wake on LAN (WoL) is a pretty common feature for network chipsets. I don't know anything about mobile networks (so take this as the semi-educated speculation that it is), but it wouldn't be a stretch to imagine WoL over 3G. It wouldn't have to be a feature advertised to end users of the SoC.
What it comes down to is "what does 'off' mean on a cell phone?"