Blender now supports soft raytraced shadows for all lamps (previously, it was only the area lamp). This works by simulating a 'soft area' size, for shadow casting purposes only. While the other lamp types simulate a square or disc-shaped area surface, omnidirectional point lamps act as if the shadows are coming from the surface of a sphere.
These lamps now have a choice between different sampling methods - the old constant jittered samples, adaptive QMC sampling, and constant QMC sampling. Adaptive QMC is by far the most efficient, often giving render times around 50% of constant sampling methods, and is the default choice for new lamps. For more details and optimisation hints, check the QMC Sampling page of the release notes.
Shadows are only calculated within the visible region that the lamp affects, so for a concentrated shadow area, spot lamps are most efficient, since the shadows are only calculated for surfaces within the spot cone. Omni point lamps are the least efficient, since every surface surrounding the lamp must be checked to see if it is in shadow or not, although when using adaptive QMC sampling, the slowdown due to this may not be very significant.
( Images by Daniel Salazar )