Q:

Omni-directional shadow mapping

What is a good/the best way to fill a cube map with depth values that are going to give me the least amount of trouble with floating point imprecision?
To get up and running I'm just writing the raw depth to the buffer, as you can imagine it's pretty terrible - I need to to improve it, but I'm not sure how.
A few tutorials on directional lights divide the depth by W and store the Z/W value in the cube map - How would I perform the depth comparison in my shadow mapping step?
The nvidia article here http://http.developer.nvidia.com/GPUGems/gpugems_ch12.html appears to do something completely different and use the dot of the light vector, presumably to counter the depth precision worsening over distance? He also scales the geometry so that it fits into the range -.5 +.5 - The article looks a bit dated, though - is this technique still reasonable?
Shader code http://pastebin.com/kNBzX4xU
Screenshot http://imgur.com/54wFI

A:

Your shader code looks a little confused to me. When you write out the depth value to the shadow map, you must divide Z/W in the pixel shader.  The raw Z value you get after multiplying by the projection matrix can't be directly compared to anything else because the projection matrix is constructed assuming that Z is going to be divided by W, so if you leave out that step you're just screwing up your numbers.
Likewise, in the code for applying the shadow map, to generate the depth value for comparison, you should transform the point by the same matrix used to render the shadow map (the same world-to-clip matrix, anyway; clearly the local-to-world will be different if it's a different object).  Then interpolate Z and W into the pixel shader and divide per-pixel, just the same way as for rendering the shadow map.
I think the errors in the screenshot you posted are due to the algorithm being incorrect, not to precision problems with the depth format. However, the simplest thing you can do to improve depth precision for projective shadows is to push out the near plane, so make sure you don't have a ridiculously small near plane value for your shadow map projection matrix.

