If I correctly understand it,
sol=Reduce[x1*x4 + x2*x5 + x3*x6 == 0 && x1*Sin[theta]*Cos[phi] + x2*Sin[theta]*Sin[phi] +
x3*Cos[phi] == 0 && x4*Sin[theta]*Cos[phi] + x5*Sin[theta]*Sin[phi] + x6*Cos[phi] == 0 &&
x1*x1 + x2*x2 + x3*x3 == 1 && x4*x4 + x5*x5 + x6*x6 == 1, {x1, x2, x3, x4, x5, x6}]
does the job. It takes some time and the output is too long to be citted here.
Addition. If I correctly understand your point, then the output of (23 is found by trials)
Table[sol[[j]] /. {phi -> 0, theta -> 0}, {j, 1, 23}]
{False, False, False, False, False, False, False, False, False, (x1 == -1 || x1 == 1) && x2 == 0 && x3 == 0 && x4 == 0 && (x5 == -1 || x5 == 1) && x6 == 0, (x2 == -Sqrt[1 - x1^2] || x2 == Sqrt[1 - x1^2]) && x3 == 0 && (x4 == -Sqrt[1 - x1^2] || x4 == Sqrt[1 - x1^2]) && -1 + x1^2 != 0 && x5 == (x1 x2 x4)/(-1 + x1^2) && x6 == 0, False, False, False, False, False, False, False, False, False, False, False, False}
shows the tenth solution is it. That solution can be displayed by
sol[[10]]
Sin[theta] == 0 && (x1 == -1 || x1 == 1) && x2 == 0 && x3 == 0 && x4 == 0 && (x5 == -1 || x5 == 1) && x6 == 0 && Cos[phi] != 0
Addition 2.The following answers the latest explanation of her/his question by OP.
sol = Solve[x1[phi, theta]*x4[phi, theta] + x2[phi, theta]*x5[phi, theta] +
x3[phi, theta]*x6[phi, theta] == 0 && x1[phi, theta]*Sin[theta]*Cos[phi] +
x2[phi, theta]*Sin[theta]*Sin[phi] + x3[phi, theta]*Cos[phi] ==
0 && x4[phi, theta]*Sin[theta]*Cos[phi] +
x5[phi, theta]*Sin[theta]*Sin[phi] + x6[phi, theta]*Cos[phi] ==
0 && x1[phi, theta]*x1[phi, theta] +
x2[phi, theta]*x2[phi, theta] + x3[phi, theta]*x3[phi, theta] ==
1 && x4[phi, theta]*x4[phi, theta] +
x5[phi, theta]*x5[phi, theta] + x6[phi, theta]*x6[phi, theta] ==
1 , {x1[phi, theta], x2[phi, theta], x3[phi, theta],x4[phi, theta], x5[phi, theta], x6[phi, theta]}]
This produces a very long output, fo example,
LeafCount[First[sol]]
8031
and a warning.
theta = 0; phi = 0; Reduce[ x1*x4 + x2*x5 + x3*x6 == 0 && x1*Sin[theta]*Cos[phi] + x2*Sin[theta]*Sin[phi] + x3*Cos[phi] == 0 && x4*Sin[theta]*Cos[phi] + x5*Sin[theta]*Sin[phi] + x6*Cos[phi] == 0 && x1*x1 + x2*x2 + x3*x3 == 1 && x4*x4 + x5*x5 + x6*x6 == 1, {x1, x2, x3, x4, x5, x6}]
? $\endgroup$