There are two categories of artifacts caused by rolling shutter: those from objects moving in the scene (such as the propeller in this example), and those that result from movement of the camera relative to the scene (especially pans, tilts, dolly movements, etc).

Those caused by camera movement (often resulting in an image that looks skewed) are somewhat easier to "fix" as you say with post processing since a correcting transformation can sometimes be applied to the entire image uniformly. Existing tools can do this with some success, but there are still some camera moves that prove to be more difficult (zooms, irregular movement, etc).

Artifacts caused by objects moving in the scene are often much more difficult to remove, at least when it comes to providing a generic solution, because "reconstruction" of the image requires fairly accurate information as to how those objects were moving. In the case of the rotating prop or wheel, it may be somewhat simple (the algorithm would still probably require user input of things like the center of rotation and speed), but in other cases, the motion may be quite complex (e.g., multiple wheels rotating in different directions/speeds, linear vs angular motion, etc). And that doesn't even account for the fact that in most cases, there will be occlusion in the source image from artifacts of the rolling shutter. That is, in the propeller example, you have patches of the background that are covered up in the source, but wouldn't be in a "fixed" image, so they need to be filled somehow.

What I'm saying is that sophisticated software may be able to do a lot in helping to correct for rolling shutter artifacts, but I don't think there will be an automatic, fix-all solution from post processing software any time soon.

For 2D-like pictures (legs of fan pictured from bottom), the fix might be possible. For 3D (propeller blades with every blade having a right and a left face), it will be not.

The software will need to choose the final position of blades in the rendered picture. There is no ideal position since the blades have been moving throughout the scan time. Whichever position we decide, there will be information missing for one/more blade. Say, left face of blade no. X needs to be rendered but the camera only captured its right face. May be assuming that all blades have same shape and information of one blade can be used in rendering other blade will fix the problem.

Also missing background will have to be reconstructed. That's another issue.

I seem to recall that Adobe Premiere Pro and/or Adobe After Effects contain a tool for mitigating rolling shutter artifacts, though I am not certain if it uses the method described in the article.

There is already a tool bundled with Nuke. I think its now in after effects (I'm pretty sure its the same tech.)

http://www.youtube.com/watch?v=Zt0u9hsPuZY