Before you try something that drastic, try experimenting with your near plane. The far plane has very little impact on z-fighting (counter-intuitively, sometimes increasing the far plane can help resolve z-fighting issues!), whereas the near plane has a huge impact.
This is because the hardware depth buffer is hyperbolic. As a very rough rule of thumb, imagine half of your precision going towards representing the objects between near and 2*near, and the other half representing objects from 2*near to far.
You can use this form to see when 24 depth buffers were introduced:
Looks like you'll be fine, except for ancient Intel cards. If you're going to support these, I'd recommend getting one off ebay for a few bucks so you can test the framerate on it too
[edit2] That list is for the automatic depth buffer that you get with your device.
If you want to create extra depth buffers, or depth buffers that can be read as textures, then support is very spotty until DX10-era cards. e.g. there's some cards that support an automatic 24-bit depth buffer, but only 16-bit depth buffers if you want to be able to bind them as a texture.