Are such high oxidation states as reported by Vojovodic et al. possible?
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} &amp; \text{values of }\Delta G, \eta, \dots &amp; \text{warnings}\\
\hline
\ce{MgBaO3} &amp; [\cdots] &amp; \text{a,b}\\
\ce{NaLaO3} &amp; [\cdots] &amp; \text{a,b}\\
\ce{CaBO3}  &amp; [\cdots] &amp; \text{b}\\
&amp;\vdots&amp;\\
\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.