Focus magic has been around for quite some time, and was extremely processor intensive when it first debuted. Nowadays it runs quite fast on most machines unless you are using a very large deblur radius. My experience with focus magic is that it is great for partially recovering badly misfocused shots, slight camera shake or subject motion blur, but is not as effective or artifact-free as other sharpening methods for properly focused photos. Be careful though, because the default settings are often way too strong. I usually let the program estimate the deblur radius, but then I always manually decrease either the percentage or the radius. Also keep in mind that Photoshop's new smart sharpen feature can also perform a deconvolution...
Focus magic and Photoshop's "smart sharpen" use a technique called a deconvolution, which has a far more ambitious goal than regular sharpening: to reverse blurring caused by some point spread function (PSF). A PSF is a technical descriptor of exactly how the image was blurred in the first place. For example, if your camera moved upward slightly during the exposure with the same velocity the whole time, the PSF could be a simple vertical line (whose length was determined by how fast the camera moved relative to the exposure time). The images below illustrate examples of potential PSF's (which can also be thought of as what happens to a point light source when it becomes blurred).
From left to right:
(1) unblurred original point source (2) simple lens blur PSF (3) vertical motion blur PSF
(4) complicated PSF from motion blur, an imperfect lens and other factors
Image deconvolution aims to reconstruct (1) using knowledge of (2)-(4), whichever the case may be. The real challenge is in accurately estimating the PSF for situations where you are not entirely sure how your camera moved, or how your camera/lens affects objects when they are really out of focus. The better you can estimate the PSF, the better you can perform the deconvolution.
An image deconvolution can either be blind/iterative or require manual input of the PSF (such as with focus magic in most situations...the automated feature is not truly blind). Perhaps the most sophisticated variety is the iterative/blind Lucy-Richardson deconvolution technique. Blind deconvolutions can be very useful for unknown or oddly-shaped PSF's.
There are a few commercial packages that come to mind which use advanced blind deconvolution techniques (in astrophotography). A number of them which can be found using a quick google search...some produce results that are definitely better than focus magic, but (last I checked) they do not have the convenience of being a photoshop plug-in, or are quite expensive. Maxim DL and ImagesPlus are two all-in-one packages which come to mind for astrophotography. However, I do not believe they offer standalone deconvolution features at a reduced cost.
A big drawback with many deconvolution techniques is that they can leave regular photographs looking unnatural when used for extreme blur correction. In astrophotography this is usually less apparent. This can be manifested in a "painterly" look or "image ringing". The example below illustrates this, although this appearance can be greatly reduced by experimenting with the radius/amount settings.
Left to right: (1) out of focus image (2) partial focus correction using focus magic deconvolution.
Note: this example is blurred because the subject is outside the depth of field; this means that each part of the foliage actually has a different PSF since it is at a different distance! The only programs which can achieve better results for situations like this are those that can let the PSF vary throughout the image.
Focus magic is particularly bad when it comes to the painterly effect because it tends to be very aggressive with noise reduction (even when disabled), but is pretty good at minimizing image ringing (where high contrast edges repeat themselves at regularly spaced distances). Another drawback is that deconvolutions require a very low noise image to be most effective. Some techniques can act to dramatically amplify noise, such as Wiener deconvolution, so be careful. Photoshop's smart sharpen tends to greatly amplify image noise, but on the other hand it also does not look as painterly. Regarless of the software package, be prepared to fiddle for quite some time with the settings of radius, blur type, amount/%, etc. in order to achieve optimal results.
Overall, image deconvolution techniques can be quite time-consuming, can require separate software packages and can be quite expensive. In my mind they are only really worth it if you need to recover from a badly blurred or out of focus (but critical) photograph. This is because their real strength is for situations where the blur radius is very large, which is unlikely to occur unless there is substantial error on the part of the photographer. One reason the deconvolution technique is so often used in astrophotography is because atmospheric distortions can make blurring much more pronounced than would otherwise occur with a regular photo.