The problem you are most likely encountering is that floating point depth buffers do not significantly help distant precision if you use them exactly like integer depth buffers. The problem and solution(s) are as follows:
With a normal perspective projection and viewport mapping, the values placed into the depth buffer vary from 0 at the near plane to 1 at the far plane, but the mapping is not linear. This means that points 2 * near in front of the eye, end up with a depth value of 0.5, leaving only 23 bits of integer precision for stuff beyond 2 * near when you use a 24 bit integer depth buffer. This naturally leads to depth fighting in far objects, when you have a small near plane.
While floating point representations of the depth buffer provide additional bits, they do not provide a favorable distribution of those bits if you continue to use the depth buffer in the same way. IEEE style 32 bit floating point numbers have 24 bits of precision between every power of two within the exponent range. This means that they have 24 bits of precsion from 0.5 (2 ^ -1) and 1.0 (2 ^ 0). As you can see, this is only one bit better than a 24 bit integer buffer for far objects. What they do provide are extra range (-MAX_FLOAT - MAX_FLOAT), and extra precision close to zero ( 24 bits from 0.25 - 0.5, 24 bits from 0.125 - 0.25, etc).
To maximize the extra precision from the floating point depth buffer one must utilize the extra properties supplied by floats. The simple solution of making the far value map to a much larger number than 1 does not work. This is because it will still be bitten by the power of two rule. If the depth buffer is set to run from 0.0 to 16.0, the values from 2 * near to far will be mapped into the 8.0 - 16.0 range. This range still has only 24 bits of precision, due to the nature of floating point numbers. What will work, is to invert the depth values, such that the near plane is at 1.0 and the far plane is at 0.0. Now, the values from the near plane to 2 * near will map into the 0.5 to 1.0 range and receive 24 bits of depth precision (typically enough for this small range). The values beyond 2 * near will be mapped to 0.0 - 0.5 and receive the 24 bits worth of mantissa and more than 6 bits worth of precision from the negative exponent values, providing around 30 bits worth of precision. It can be pushed further, by mapping the near value to a number greater than 0.0, but the gains are going to be significantly diminished.
Finally, the precision cannot be improved in a meaningful way by using both positive and negative numbers in the depth buffer. Since precision concentrates around 0.0, this would result in all the precision being concentrated near 2 * near, which is typically not desirable.
To get the depth inverted, you can either change the values sent to depth range to be the reverse of what you would normally use, or you can bake a scale of (1,1,-1) at the end of the projection calculation. With either one, you need to reverse your depth test function and polygon offset values. With the scaling trick, you need to change the front-face direction. (CW versus CCW) The projection matrix trick might provide slightly better results, because it does the computations pre-clip and pre-projection, but I have not personally been able to find a difference. Also, remember that if you plan to try to use a depth range value outside [0,1], you need to use glDepthRangeNV.
As for shadow mapping and depth fighting, be careful searching for more precision. When you are trying to compare values like this, additional precision means that it is harder to get equality. If the code generating the depth values is not doing things right, adding more precision will often make things worse instead of better.