Solve returns solution that isn't (always) one

You can instruct Solve to generate all conditions using MaxExtraConditions, or you can use Reduce instead of Solve.

Solve[a + Sqrt[x^2 - b] == 0, x, MaxExtraConditions -> All]

During evaluation of Solve::useq: The answer found by Solve contains equational condition(s) {0==-a-Sqrt[a^2],0==-a-Sqrt[a^2]}. A likely reason for this is that the solution set depends on branch cuts of Wolfram Language functions.
(* {{x -> 
   ConditionalExpression[-Sqrt[a^2 + b], a + Sqrt[a^2] == 0]}, {x -> 
   ConditionalExpression[Sqrt[a^2 + b], a + Sqrt[a^2] == 0]}} *)

Reduce[a + Sqrt[x^2 - b] == 0, x]

During evaluation of Reduce::useq: The answer found by Reduce contains unsolved equation(s) {0==-a-Sqrt[a^2],0==-a-Sqrt[a^2]}. A likely reason for this is that the solution set depends on branch cuts of Wolfram Language functions.
(* (0 == -a - Sqrt[a^2] && 
   x == -Sqrt[a^2 + b]) || (0 == -a - Sqrt[a^2] && x == Sqrt[a^2 + b]) *)

Quoting from the Solve documentation:

Solve gives generic solutions only. Solutions that are valid only when continuous parameters satisfy equations are removed. Additional solutions can be obtained by using nondefault settings for MaxExtraConditions.