Question: "solve" issues

Following set of equations will solve and give exact solutions for x1, x2, x5.

solve({
x1^2-x2^2-x3+x4=0,
(x2+1)^2-x5 = 0,
125+x1 - x2 = 0,
1+x3 - x4 = 0,
x8*x6+x7 - x8^2= 0,
x9*x6+x7 - x9^2-x3 = 0,
y2*x6+x7 - x5-y2^2 = 0,
y1*x6+x7+x5 - x5-y1^2-x4 = 0
},
[x1, x2, x3, x4, x5, x6, x7, x8, x9, y1, y2]);

However if I add the equation x4+(x1-x2-1)*(x1+x2+1) = 0 to the set of input equations, "solve" will not find any solution at all, although the new equation is not contradicting any of the previous equations.

If I change the "125" in the input equations to "1", then, even with the new equation just added, "solve" will find some solution.  How do I get the same solution for x1, x2 and x5 even after adding the new equation?

Can someone help? Thanks in advance.