Would something like what was proposed by Mike Bayer be considered?
> A new token called "tuple_order" or something > > INSERT INTO table (a, b, c) VALUES ((1, 2, 3), (4, 5, 6), ...) RETURNING table.id, inserted.tuple_order > > tuple_order would be incrementing values 1, 2, 3, 4, 5, ... which correlate the each row delivered by RETURNING to each entry in the VALUES clause, in the order they were stated in that VALUES clause, that is entry (1, 2, 3) would be tuple_order 1, entry (4, 5, 6) would be tuple order 2, etc.
Personally, yes, a declarative syntax specifying the desired behavior and thus giving the system permission to potentially trade optimizations for a deterministic output is the way forward. Ideally current and future optimizations/performance characteristics could be maintained even in the presence of this option but ultimately the system would be compelled to return records in the specified order no matter the cost. For bonus points, the impact on queries that do not specify this option should be as close to nothing as possible - though I/O is likely to make some increase negligible.