Oxidation states are just numbers, a bookkeeping tool for chemistry. These hardly ever correspond to anything observable. Point in case: hypofluorous acid $\ce{HOF}$, see for example the oxidation state of oxygen and of fluorine in the confines of the definition. Maybe also of interst in that regard is the introduction to "oxidation state"/"oxidation number" in general.
Therefore instead of asking whether the oxidation states are stable, one should ask if the bulk/ molecular structure is stable.
When it comes to computationally aided catalyst design, you can pretty much use the entire periodic table to play with. It is a matter of interpreting the results that count, and obviously if experiment can reproduce such predictions. Where you start becomes a matter of taste and starting with perovskites is as good a guess as any.
The authors of the publication make quite an effort, calculating hundreds of potential catalysts. However, they also indicate problems within their methodology. Quoting from the supporting information:
3 Oxygen evolution data
[...]
\begin{array}{lcl}
\text{formula} & \text{values of }\Delta G, \eta, \dots & \text{warnings}\\
\hline
\ce{MgBaO3} & [\cdots] & \text{a,b}\\
\ce{NaLaO3} & [\cdots] & \text{a,b}\\
\ce{CaBO3} & [\cdots] & \text{b}\\
&\vdots&\\
\hline
\end{array}
a: One or more runs did not converge or failed in Quantum Espresso, missing adsorbates are reconstructed from successful runs using scaling
b: Changes in atomic positions of greater than 5.5 angstrom found in the slab or adsorbate during optimization, typically indicates structural instability
[...]
And there are a lot more unstable species.
TL;DR: Basically, in these extreme cases, where you would observe abnormal oxidation states, the calculation also predicted that the bulk/ molecular structure is not stable.