I cannot give first hand information. I do recall that Claes Johnson and his students were testing and analyzing this in the 80's. The convergence analysis was solid but they dropped  it (I think I recall) because of the difficulty of finding a streamwise ordering especially when the flow has recirculation. (Their idea at the time was to do several sweeps in different  orderings so that each variable has at least one in a streamwise direction.) I think this is what Wittum addressed (again---based on my imperfect memory). I suggest  you email Johnson and Wittum directly.  They may even have codes available so  you can test it easily.  It is a good idea worth reconsidering. Sorry I dont recall more. I hope this is helpful.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.503

hope this is helpful

Thank you both for your helpful answers. Concerning the linked paper by Hackbusch & Probst, I understand that the structured problem is a much simpler subproblem of the described one on general unstructured meshes, but still I am wondering about practical experiences with the implementation and performance of the method on structured meshes.

In chapter 7.7 of the book "An Introduction to Multigrid Methods" by P. Wesseling (1992),  I found a description of the four-direction point Gauss-Seidel scheme which basically consists of swapping the sweeping directions of Gauss-Seidel. Nevertheless, I'm still interested in real-world applications and will try to contact Claes Johnson.

Sweeping in all 4 directions will give a desired result, but  smoothing will be 4 times more expensive. In addition, this would be difficult to implement on non-structured grids. But this is a good strategy for recirculating flows. You may also want to look at the work by Bey and Wittum (Appl. Numer. Math. 23(1997), 177-192). One potential variant of a black-box implementation of downwind ordering, studied by Hackbusch and Probst (Numer. Lin. Algebra 4(1997), 85-102 is the use of Tarjan's algorithm (a version of depth-first search applied to the graph associated with the sparse matrix). Additional useful literature includes H. Elman and M. Chernesky's work on ordering effects for smoothers in the case of convection problems in 1D. We have recently looked at truncated ILU smoothers for convection-dominated problems, with fairly encouraging results (the smoothing is just slightly more expensive than Jacobi, but fairly robust).

Thank you a lot for the references and the remarks. I'll take a close look.

Bit late, but we recently wrote a paper on approximating an optimal ordering for Gauss-Seidel (or "sweeping" in transport literature) algebraically when there are cycles in the mesh. This was for pure transport on high-order meshes, where high-order meshes induce non-triangular components in the matrix, but the same concept should work to algebraically find a "good" ordering for Gauss-Seidel on convection-dominated problems. See:

Preprint An Efficient Sweep-based Solver for the SNS_{N} Equations on...

It is based on an O(n) pre-processing steps that approximately finds the maximum acyclic subgraph of the matrix equation.