maths nested superscripts and subscripts displayed incorrectly inline

I think you can justly regard this strange behaviour as kind of a bug in TeX's sub- and superscript positioning algorithm; it doesn't make sense that both the sub- and the superscript are raised. See below for some suggestions on how to fix the problem. At the end I offer a new positioning algorithm, and I compare it with the old algorithm. (Sorry for the length of this answer!)

What's happening?

The positioning algorithm is laid down in Rule 18 of Appendix G in the TeXbook. Here's what's happening: first, tentative positions of the sub- and superscripts are defined (Rules 18c and 18d). The problem arises in Rule 18e: only if the sub- and superscript are too close together (less than four times the default rule thickness, according to the tentative positions), TeX makes sure that the bottom of the superscript is at least as high above the baseline as 80% of the x-height. In this case, the superscript may be raised more than necessary for achieving the minimum distance of four times the default rule thickness, and then the subscript will be raised, too!

To illustrate the problem, I use an m as a subscript, and a rule with height 0 and different depths as superscripts:

In the first case, the depth is 0.34ex, in the second case it's 0.35ex: an imperceptible difference leading to rather different outputs. I don't think that this behaviour is desirable. Note that this only happens due to the m having a small height, not for letters like f with ascenders.

\documentclass{article}
\newcommand\test[1]{\omega_m^{\rule[-#1ex]{1pt}{#1ex}}}
\begin{document}
$\test{0.34}$ versus $\test{0.35}$
\end{document}

Let me point out that the same effect can occur in \displaystyle: then superscripts are set a bit higher by default so that the effect appears at a depth of 0.46ex versus 0.47ex. So it is a case of good luck that \displaystyle helps in your case (as observed in David's answer). Let me point out that in "cramped" style (as used under \overline and \sqrt) the effect can be quite drastic: $\overline{a_n^ia_n^j}$ gives

Possible ways to fix the problem

I see at least three completely different ways out of the problem; I'm not sure which one to prefer. The first idea (see David's second comment to this answer) is to add a strut to the subscript to give it so much height that TeX won't raise it. The following code defines a \scriptstrut that is just large enough; however, I think that the output is still not optimal: the second superscript is raised too much.

\documentclass{article}
\makeatletter
\AtBeginDocument{%
  \check@mathfonts               % initialize math fonts
  \dimen@=\fontdimen5\textfont2  % x-height
  \multiply\dimen@ by 4
  \divide  \dimen@ by 5          % 80% of the x-height
  \advance \dimen@ by \fontdimen17\textfont2
  \@tempdima=\fontdimen8\textfont3
  \multiply\@tempdima by 4       % 4x the default rule thickness
  \advance \dimen@ by -\@tempdima
  \edef\scriptstrut{\noexpand\rule{0pt}{\the\dimen@}}%
  }
\makeatother
\begin{document}
$\omega_{m_{ij}}^r$ versus $\omega_{m_{ij}\scriptstrut}^{r_{ij+1}}$
\end{document}

Now you'd have to add a \scriptstrut to all the subscripts that are raised too high. One could try to automatize this by making the underscore _ active (see also mafp's second comment), but it's not easy to do this in a safe way: note that, e.g., $a_\frac12$ is valid (albeit not recommendable) TeX code.

Here's my second idea: by default, TeX places subscripts lower if a superscript is present. You can prevent this by adding

\makeatletter
\AtBeginDocument{%
  \check@mathfonts %initialize math fonts
  \fontdimen17\textfont2=\fontdimen16\textfont2
  }
\makeatother

to your preamble. This doesn't completely suppress the problem, but it makes it a lot less visible. However, there could be other side effects.

The new positioning algorithm

Probably the best way is to use another algorithm altogether for the vertical positioning of a sub-/superscript combination. I offer such a new algorithm in the code below, where I define an \nss command (like "natural sub- and superscripts") that takes three arguments, the 2nd being the sub- and the 3rd being the superscript of the 1st.

The rules I use are as follows, keeping as close to the original algorithm as possible: Use the tentative default positions as the TeX engine would do it. To achieve that the sub- and superscript are at least four times the default rule thickness apart, raise the superscript, but only as long as its bottom is at most 80% of the x-height above the baseline. If the distance between sub- and superscript is still too small, lower the subscript.

\documentclass{article}
\usepackage{mathtools}
\makeatletter
\newcommand*\nss[3]{%
  \begingroup
  \setbox0\hbox{$\m@th\scriptstyle\cramped{#2}$}%
  \setbox2\hbox{$\m@th\scriptstyle#3$}%
  \dimen@=\fontdimen8\textfont3
  \multiply\dimen@ by 4             % 4x the default rule thickness
  \advance \dimen@ by \ht0
  \advance \dimen@ by -\fontdimen17\textfont2
  \@tempdima=\fontdimen5\textfont2  % x-height
  \multiply\@tempdima by 4
  \divide  \@tempdima by 5          % 80% of the x-height
  % Modifications are only necessary if the top of the subscript is not that high:
  \ifdim\dimen@<\@tempdima
    \ht0=0pt                        % don't let the subscript interfere
    \@tempdima=\fontdimen5\textfont2
    \divide\@tempdima by 4          % 25% of the x-height
    \advance \dimen@ by -\@tempdima % if >0, add to depth of superscript!
    \ifdim\dimen@>0pt
      \@tempdima=\dp2
      \advance\@tempdima by \dimen@
      \dp2=\@tempdima
    \fi
  \fi
  #1_{\box0}^{\box2}%
  \endgroup
  }
\makeatother
\begin{document}
\begin{tabbing}
   Original: $\omega_{m_{ij}}^{r_{ij+1}}$,\,
\= improved: $\nss{\omega}{m_{ij}}{r_{ij+1}}$. \\
   Original: $\overline{a_n^i a_n^j}\,$,
\> improved: $\overline{\nss{a}{n}{i} \nss{a}{n}{j}}\,$.
\end{tabbing}
\end{document}

Finally, a somewhat more extensive comparison between the original and the improved algorithm. I use a box of width 2pt as a subscript and a box of width 1pt as a superscript. The subscript has varying heights (but depth 0pt), the superscript has varying depths (but height 0pt). You see a lot of wobbling with the original algorithm!

\documentclass{article}
\usepackage{mathtools}
\makeatletter
\newcommand*\nss[3]{...} % insert code from above!!!
\makeatother
\newcommand\oss[3]{#1_{#2}^{#3}}
\newcommand\test[3]{#1{\omega}{\rule{2pt}{#3pt}}{\rule[-#2pt]{1pt}{#2pt}}}
\newcommand\compare[2]{\test#1{#2}{1}\test#1{#2}{2}\test#1{#2}{3}\test#1{#2}{4}}
\newcommand\oneline[1]{\compare\oss{#1}\qquad\compare\nss{#1}}
\newcommand\threelines[1]{%
  \leavevmode\rlap{Original:}\hphantom{$\compare\oss1$}\qquad Improved: \par
  $#1{\oneline2}$ \par
  $#1{\oneline3}$ \par
  $#1{\oneline4}$ \par}
\begin{document}
\textbf{Cramped style} \par
\threelines\cramped    \medskip
\textbf{Text style}    \par
\threelines\textstyle  \medskip
\textbf{Display style} \par
\threelines\displaystyle
\end{document}

The default positions of sub and superscripts are closer to the baseline in textstyle as TeX tries to maximise the chance that the expression does not disturb the paragraph line spacing.

Your first example is the standard setting for inline math, however with the larger scripts caused by the subscripting, TeX has to move them further apart.

This is standard layout, however you can use \displaystyle to force the less cramped setting even in inline math if line spacing is not a concern.