Interestingly, we are already trying to do the right thing here.  Try this code which adds a call to warning().

try
  z = zeros (2^53,1);
catch ME
  disp ('in catch block');
  warning ("warning in catch block");
  rethrow (ME);
end

which results in

in catch block
warning: warning in catch block
warning: called from
    blah at line 5 column 3

error: out of memory or dimension too large for Octave's index type
error: called from
    blah at line 2 column 5

So, apparently the warning function does flush stdout before proceeding.  Given that Octave is an exception state, performance isn't important.  It seems like rethrow() should borrow the code that warning() uses and flush stdout before proceeding.

Sample code:

try
  z = zeros (2^53,1);
catch ME
  disp ('in catch block');
  rethrow (ME);
end

When run in Octave it produces the output:

error: out of memory or dimension too large for Octave's index type
error: called from
    tst_rethrow_ordering at line 2 column 5
in catch block

In Matlab, the code in the catch block that precedes the rethrow () call is executed first and printed first.  This seems more logical as execution is from top to bottom.

One can resolve this by adding "fflush (stdout)" before the call to rethrow(), but it would probably be better to have rethrow do the flushing.