I'll write some fragment of thoughts here.
First some known results. All the lambda cube is consistent (and normalizing, though I didn't mention it in the question, I'm also interested in that). A hierarchical structure that $\star_i : \star_{i+1}$ and the rule $(\star_i, \star_j, \star_k)$ only if $k > i, j$ is consistent, by @AndrejBauer 's construction (I came across a webpage detailing that, but I lost the URL, I'll link when I found it). And system $U^-$ is inconsistent, suffering from Girard's paradox.
Next, some graph theoretic reductions. Consider the PTS as a hypergraph with 2- and 3-edges. Then one can just consider the connected components. Also, an embedding $\lambda S_1 \to \lambda S_2$ of two PTS's (i.e. a map of the vertices that preserve the edges) reflects consistency: the consistency of $\lambda S_2$ implies that of $\lambda S_1$, and the reverse implication for inconsistency.
I think there is some way to chop off some wandering edges, but I haven't got into that yet. But the idea is to define a weak dependency between sorts. Say $\star_i$ weakly depends on $\star_j$ if for some expression $\Gamma, x:N \vdash A:M:\star_i$ where $N:\star_j$, $A$ can contain $x$ in a well-typed fashion. If there is no weak dependency, the rule $(\star_i, \star_j, \star_k)$ can probably be translated away by a similar method of translation from $\lambda P$ to $\lambda ^\to$, see Barendregt's Lambda Calculi with Types.
I fancy if we make enough reductions, we might determine the consistency of all PTS's. The hope lies in that most PTS's are probably trivially inconsistent because they are just too entangled and impredicative :(