> 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.

Maybe, but it looks like a problem of unscrambling an egg. The true image has been smeared over the sensor, superimposed on itself a bit. Maybe there is a good enough solution for the problem of finding the true image, but I can't imagine it to be computationally inexpensive.