Is INSERT RETURNING guaranteed to return things in the "right" order?

I don't see anything in the documentation that guarantees an order for RETURNING so I don't think you can depend on it. Odds are that the RETURNING order will match the VALUES order but I don't see any guarantees about what order the VALUES will be inserted in either; the VALUES are almost certainly going to be insert in order from left to right but again, there is no documented guarantee.

Also, the relational model is set based so ordering is something applied by the user rather than an inherent property of a relation. In general, if there is no way to explicitly specify an ordering, there is no implied ordering.

Execute summary: the ordering you're seeing is probably what will always happen but it is not guaranteed so don't depend on it.

While the documentation isn't entirely clear, it does state that:

If the INSERT command contains a RETURNING clause, the result will be similar to that of a SELECT statement containing the columns and values defined in the RETURNING list, computed over the row(s) inserted by the command.

Now "similar to" isn't an ironclad guarantee, and I've raised this for discussion on the mailing list ... but in practice, PostgreSQL won't mess with the order of values in RETURNING. It's unlikely we'll ever be able to even if we want to for optimisation, because too many apps rely on it being ordered the same as the input.

So... for INSERT INTO ... VALUES (...), (...), ... RETURNING ... and for INSERT INTO ... SELECT ... ORDER BY ... RETURNING ... it should be safe to assume that the result relation is the in the same order as the input.

While this won't help you now, 9.1 will include "writeable common table expressions". That's the official name for the WITH syntax. (Wikipedia.)

This new ability should let you place your INSERT ... RETURNING inside a WITH, give an alias, and then SELECT against that with a specific ordering with a plain old ORDER BY clause.