If you then add a charge outside of the constructed Gaussian surface, the Q enclosed remains the same. Therefore the calculation and the E calculated would be the same as well.
This is incorrect. Gauss’ law only tells you about the net flux. It does not tell you about the E field. So, indeed, adding a charge outside the surface will not change the net flux, but it can and does change the field.
The only way that you can use Gauss’ law to go from net flux to field is in cases where there is a high degree of symmetry such that there can be only one possible value of the field that both satisfies Gauss’ law and the symmetry. In your example, there is such symmetry without the charge, but adding the charge removes the symmetry.
After removing that symmetry there are many configurations of field that are consistent with the net flux, but only one of those is the actual field. Which one cannot be determined by Gauss’ law alone.