OK, how about this, instead of your 3D array of booleans, make a 3D array of arrays of atom numbers (integers, basically making a 4D array) making your virtual volume. In other words, each 3D position holds a list of nearby atoms. The array of atom numbers only needs to be as large as the largest possible number of atoms that can be within three lattice spaces away from that position. (You could add other indexes to that array of atom numbers to indicate, for example, if that 3D position can properly support an atom or other things.) Then you will also have a second array of atoms that stores the 3D position of each atom indexed by atom number. (This array could also store other information, such as potential moves for the atom, if you wanted to.)
When you first start you fill in your atom array with the positions of each of the atoms, and then put that atom number in each of the volume array points that are within three lattice positions from that atom's position. Now, your atoms can only move into locations where their atom number is the only atom number for that position in the volume and it can be supported by the atoms below. When an atom moves, remove it from all of the points in the volume array within three lattice positions of the old position, and then re-add it to all of the lattice points within three positions from the new position. (For bonus points, just remove it from the positions that it got far enough from and just add it to the positions it got close enough too, instead of removing and re-adding it to some of the locations it was already marked for.)
So, for example (assuming a cubic lattice, for simplicity), if you have an atom #1 at X,Y,Z position 15, 15, 15, then all points within the volume that are within three lattice spaces of that point will have atom #1 in their atom array list. If atom #2 is at 20, 15, 15 then position 16, 15, 15 would only have atom #1 in its atom array list, but position 17, 15, 15 would have atoms #1 & #2 in its list. So, if position 16, 15, 15 could support atom #1 (i.e. the atoms below support it) it could move there, but it couldn't move to 17, 15, 15 because that's too close to atom #2.
Obviously this will take a lot more memory and a longer initial setup, but I think it should be really fast once it gets started.
P.S. I'm curious about the shape of your lattice. I'm having trouble creating a cohesive picture of it with your "5*5*3 volume around it" and "24 different directions of move in total" comments.
The difference between intelligence and stupidity is that intelligence has its limits.