My answer will be a bit more charitable than Willie's. There is an algorithm (sort of) to compute the dimension of the solution space of the Killing equation. Whether it is simple or not, you can decide for yourself.
The Killing equation is an example of an (overdetermined) equation of finite type. This means that knowing the solution (up to finitely many derivatives) at one point is sufficient to determine it everywhere (up to possible multi-valuedness, when the domain is not simply connected). This property is a stronger version of something like analytic continuation. In the case of analytic continuation, the knowledge of all derivatives of a holomorphic function at a point determines it everywhere. For functions satisfying equations of finite type, we only need the knowledge of the derivatives up to some finite number, say $k$, and then all higher derivatives can be deduced from the known ones. To determine the full solution space one need only study the allowed values of the first $k$ derivatives (also known as the $k$-jet). Under the simplifying assumption that the subset of admissible values of the $k$-jet at a point is smooth, as well as varies smoothly from point to point, the the dimension of the subset of admissible $k$-jets will be the dimension of the solution space (at least on a simply-connected domain). (I'm actually not sure how this theory works when this simplifying assumption doesn't hold, but I think that any irregularities in the geometry of the set of admissible $k$-jets will only reduce the dimension of the solution space).
Just a few more details about how the the continuation of a solution from a point to the whole domain. Let me denote the space of $k$-jets by $J^k$ and the subset of admissible $k$-jets by $\mathcal{E} \subset J^k$. By our assumption, $\mathcal{E}$ is a smooth bundle over the domain. Since give a $k$-jet of the solution we can compute the $(k+1)$-jet as well, we can define a hyperplane distribution in $T\mathcal{E}$ (hyperplanes of the same dimension as the domain) to which the jet extended graph of any solution must be tangent. This distribution will actually be integrable and hence, by the Frobenius theorem, will define a foliation on $\mathcal{E}$. Each leaf of this foliation will be the $k$-jet extended graph of a (possibly multivalued) solution on the whole domain.
Why does the Killing equation have this structure? The answer follows from the following exercise: prove that if $\nabla_\mu \xi_\nu + \nabla_\nu \xi_\mu = 0$, then $\nabla_{(\mu_1} \cdots \nabla_{\mu_l)} \xi_\nu = 0$ for any $l\ge 2$. A bit of knowledge of the theory of Yang diagrams and the Littlewood-Richardson rule will give you the answer without any explicit calculation, but it's not necessary to take that approach.
So, for the Killing equation, we can take $k=1$. Note that this means that the dimension of the solution space cannot be greater than the $1$-jet of $\xi_\mu$. In $4$ dimensions, this number is $4+4*4 = 20$. However, the Killing equation itself already tells us that $4*(4+1)/2=10$ of these $20$ components are determined by the equation, leaving at most $20-10 = 10$ as an upper bound on the dimension of the space of admissible jets, and hence the solution space. As is well known, this bound is in fact saturated on maximally symmetric spaces (Minkowski or (A)dS).
It remains to identify all other constraints on the admissible $1$-jets of Killing vectors. In general, these are known as integrability conditions. For the Killing equation, it is known that a complete list of integrability conditions is given by $\mathcal{L}_\xi \nabla_{\mu_1} \cdots \nabla_{\mu_l} R_{\alpha \beta \gamma \delta} = 0$, that is, the Lie derivative of the Riemann tensor and all of its covariant derivatives must vanish. I believe that this is what Willie meant under in the somewhat confusing phrasing "By virtue of the definition, Killing vectors are orthogonal to the gradient of curvature invariants." So, if you known enough about the Riemann tensor to conclude that after a sufficiently large $l$ you do not get any new constraints of the $1$-jet of $\xi_\mu$, you can apply the theory described above and obtain the dimension of the space of Killing vectors. (One should not think that it is easy to figure out how to know "sufficiently much" about the Riemann tensor in this way.) One way this happens is when some finite $l$ is sufficient to reduce the admissible $1$-jets to $\xi_\mu = 0$ and $\nabla_{[\mu} \xi_{\nu]} = 0$ at every point, meaning that the dimension of the solution space is $0$. This is the case for generic metrics.
While I gave the list of integrability conditions in terms of the Riemann tensor and its covariant derivatives, it's conceptually straight forward to convert them to formulas that use the tetrad analogs of these quantities.
