as long as there is anything to key onto it's possible to remove the shake algorithmically
Why the requirement? The phone already has accelerometers, doesn't it?
In any case, less hake should still be easier for the phone to deal with. Those algorithms aren't flawless.
Even when you stabilize the footage afterwards (digitally, not by stabilizing the sensor), there will be motion blur due to the lower shutter speed.