This works perfectly for isometric cubes, and is what I do currently.
If you imagine two long rectangles, one in each of your two hands, and pretend they are two cars passing each other in an isometric world, you will see that pretty soon, one car's screen.y position will be below the other before it's clear of the vehicle which should actually be occluding part of it.
I thought about this for a bit, and I have a feeling that as long as everything is touching the ground, then making covering loops is impossible, and so there exist a simple ordering you can compute.
The ordering is as follows: I'm assuming the isometric rendering of a map as a 45 degrees tilted square, and I'm only considering tile ordering just for simplicity but it should generalize fine. The uppermost tile is where you want to start rendering. From there, you render following the two 45 degree diagonals until you are done (so you don't only look at the y axis). Once this is done, you restart the process from the tile just below the uppermost corner, and so on. This ordering makes sure that all rectangular objects that are aligned with the 45 degree diagonals are rendered correctly.
Now you need an additional trick to render rectangular objects that are transversal to those diagonals correctly. What you do is you keep track of the boundaries of all such objects, so that the rendering loop described above can tell when it encounters one. Once it encounters it, it pauses rendering the current diagonal and considers it temporarily complete. The diagonal on the other side still needs to be rendered fully though --- or at least as far as possible with the same stopping condition. The next rendering pass will likely at some point re-encounter the same transversal object, just at a further point. Stop again, start the next diagonal. Once the rendering encounters the lowest and last part of the transversal object, then that object can be rendered, and the first stopped diagonal can be resumed (and after this resume all the paused diagonals in order).
This should always give you the correct order to render everything without errors. Let me know if this made sense, otherwise I can try to clarify.
This is an interesting approach, though I dont think it will work. Vehicles/units move pixel by pixel, not tile by tile. Each wall tile in my game takes up one tile, and walls sit on the edge of a tile. I dont think this will handle unit/wall rendering order properly unless I also form larger shapes from the walls.
I forget the exact algorithm, but you can factor in your x with y. For right-facing sides, anything at the same y with a greater x is in front of a lesser x, and vice versa for left-facing sides.
If you imagine two long rectangles, one in each of your two hands, and pretend they are two cars passing each other in an isometric world, you will see that pretty soon, one car's screen.y position will be below the other before it's clear of the vehicle which should actually be occluding part of it.