I'm going to ignore your commentary about the possible ordering of four supplied quad vertices, as I don't think it's relevant to the question.
The question(s) as I understand them, are:
(a) can you supply only two corner verticies of an axis-aligned 3d quad, and automatically determine the normal. (short answer: no, not in the general case)
(b) how can you generate the four vertices of an axis-aligned quad given the corner vertices when you know the normal?
(c) is this a worthwhile optimization of anything useful (short answer: probably not)
The reason you can't omit the quad-normal (or axis alignment) is that if the corner verticies happen to lie on two axis-aligned planes, you will have no way to disambiguate which one you wanted.
Imagine the (x,y,z) corner points (0,0,0) and (1,0,0)
Did you want a y-axis aligned plane or a z-axis aligned plane? There is no way to know without giving it the normal, because both the y and z coordinates match.
This becomes apparent when you generate the coordinates for the y-axis and z-axis aligned quads... because both of them share the two points above as corners.
y-axis quad : (0,0,0) (0,0,1) (1,0,0) (1,0,1)
z-axis quad : (0,0,0) (0,1,0) (1,0,0) (1,1,0)
To generate the 4 corners of the axis-aligned quad given the normal, you are going to permutate the coordinates around the other axis. This becomes simpler if you think about it in 2d on the axis.
Given two 2d corners: (a,b) (c,d)
The four corners are: (a,b) (a,d) (c,d) (c,b)
For example: (0,1) (2,3) -> (0,1) (0,3) (2,3) (2,1)
To do this in 3d, you simply add the 3rd coordinate for axis-alignment without changing it:
X-aligned: (X,a,b) (X,c,d) -> (X,a,b) (X,a,d) (X,c,d) (X,c,b)
Y-aligned: (a,Y,b) (c,Y,d) -> (a,Y,b) (a,Y,d) (c,Y,d) (c,Y,b)
Z-aligned: (a,b,Z) (c,d,Z) -> (a,b,Z) (z,d,Z) (c,d,Z) (c,b,Z)
The reason this probably isn't a useful optimization to do on 3d GPUs has to do with how GPUs handle conditionals.
In the GPU, if you put in a switch, which you must have to choose between the three axis alignment cases above, ALL GPU cores need to follow every branch of the switch, ignoring the cases that don't apply to them. This means you are running all three lines above on all GPU cores for all QUADS in your quad list. The GPU will run the vertex code faster if you supply the extra vertices so it doesn't have to run the conditional.
Also, by supplying the axis information in a packed form (one byte), you are going to unalign the entire quad vertex buffer. Instead of each Quad being 4x3x16bits, each quad will be 2x3x16bits + 8bits (axis). If you are just loading a buffer and sending it to the GPU it's probably fine but if your CPU is generating the quad-buffer, then the unaligned 16bit floats could potentially slow things down quite a bit in the CPU generation.
Are there situations where this could produce a speedup? Maybe.... If you have pre-calculated quad-buffers with extremely large numbers of only axis-aligned-quads, then you could reduce the size of those buffers substantially. You could even remove the axis-alignment byte, by instead supplying a per-draw-call list of three ints (# x-axis aligned, # y-axis aligned, # z-axis aligned) and then pre-order the quad-corner list so all the x-axis aligned quad are first, followed by y-axis-aligned, followed by z-axis aligned. This would basically make the size of your "axis aligned quad draw" buffer down by half, so for very large numbers of only axis aligned quads, that could be relevant.
However, I can't imagine the application for which this is relevant.
Voxel bricks can be drawn faster by using the GPU for the ray-marching of the voxel grid itself.
Further, even if you want to use the CPU to do it, voxel bricks are generally uniform size, so you don't need the flexibility of arbitrary corners, and can instead just supply the center point of the voxel and the face-number (1-6).