System Information
OS: Ubuntu Linux 16.04, kernel 4.4.0
GPU: EVGA GeForce GTX 950 FTW

Blender Version
Broken: 2.77a abf6f08

Short description of error
Okay, the above description is verbose and confusing. I'll use this render to display the issue:

It looks like it's a depth clipping issue (is that the right term?), in which case I'm not entirely sure it is something that can be resolved.

Exact steps for others to reproduce the error

1. Add a plane to the scene
2. Add a cube to the scene. Raise it so that its bottom face is perfectly aligned with the plane
3. Create a new material for the cube, and make it a Volume Scatter material.
4. Add a second plane to the scene, placing it below the first one, then texture it. Alternatively, put an environment map onto the world shader.
5. Render.

Alternatively, just use this .blend file: