Nearest Point

I think what you really want is a Voronoi diagram (related to Delaunay triangulation), which will give you the set of convex regions. Then for fast lookup, you could then organize those regions into a BSP tree.

A quick-n-dirty solution(not optimal) would be to just divide the cubes into smaller cubes, like a 3D grid. Each subcube will have a coordinate, let's say (cx,cy,cz). Each of these 2^16 points belongs only to 1 subcube. This simplifies things. Given a new point(x,y,z), it's very easy to determine in which subcube(cx,cy,cz) it belongs. From there on, you just search for the nearest point only in that subcube, and ignore all the rest. In the (unlikely) possibility that a subcube is completely empty, you can flag it as such and so you don't search in it for nearest points, but in its neighbours. A hierarchical structure(like an octree) instead of a grid would be better.

A Voronoi diagram would work, but again I don't know how to generate it. In that case it seems like I need an efficient way to test for redundant linear constraints so that I could prune the majority of the bounding planes surrounding each point. But I can't think of any algorithm to manage this which wouldn't be prohibitively expensive.

Check out Octree's (which is the term for the ideas above)!

You can get a big speed boost using this!

mikeman has the right idea. It's sometimes called the Spanish Moss or Hanging Moss algorithm. It's incredibly simple and straightforward, far easier to update in real-time (if your points are moving) than other silly structures, has consistent performance across the space (unlike the death planes of quad/oct-trees), etc... Seriously, don't overcomplicate this.

Pick a good resolution, and partition all your points into a uniform grid. Given a new point, it's O(1) to decide which grid cell it lies in. Test against all points in that cell and each of it's neighbors (because of edge cases). Technically, you need to spiral out if there are no nearby points.

With regard to the hanging moss algorithm...

To be completely honest, the positions of the fixed points aren't totally random... they will always be along a line connecting two of 16 special points. These 16 special points exist at the corners of a cube stretching from <0,0,0> to <1, 1, 1>, the corners of a cube stretching from <0,0,0> to <0.5, 0.5, 0.5> (minus the redundant origin point), and the point at <0.75, 0.75, 0.75>. While this creates a decent spiderweb, there are still a fair number of gaps and clusters. Hence spiraling will happen frequently, and the number of points which will need to be searched will grow rapidly as more lines intersect the search space.

I think that using an octree may help to mitigate the clustering problem, but I'm left with the problem that I don't know how to test edge cases with an octree.

This problem is called a nearest neighbor search. You could use an octree or a kd-tree or a similiar type of tree. First you use the tree to quickly find the node that contains the query point and find the point associated with that node that is closest to the query point. Now you have an upper bound on the distance between the query point and the closest point. That gives you a sphere you can use to cull nodes as you search for the closest point (and if you come across any points that are even closer you use them instead and get an even tighter upper bound).