It seems that if the blur is caused by moving the camera you can try to find the direction the movement happend and restore the original photograph quite nicely afterwards.
Topaz Labs has had a Photoshop plugin out for some time now (InFocus) that does the same thing. It cuts off at a fairly low blur radius, though, since it's intended for photo correction rather than forensic retrieval, and ringing can get pretty severe even at a small pixel radius.
What sets the Adobe tool apart from the rest (so far) is that you can define a non-linear path for motion blur. From what was said at the demo, there seems to be some hope for automatically determining a non-linear motion path. That would be really cool.
Blurity author here. I'm happy to say that Blurity does exactly what you're requesting in your second paragraph: it can "automatically determine a non-linear motion path" using true blind deconvolution. Although Blurity is a commercial product, the watermarked trial is free. I'd be curious to hear your reactions.
And other program I'be heard but haven't tried before is UnShake: http://www.zen147963.zen.co.uk/Unshake/
It seems that if the blur is caused by moving the camera you can try to find the direction the movement happend and restore the original photograph quite nicely afterwards.