-----> ahaheh. I'm slow to the party. Anyway, yeah, drawing based on the 'rightmost' tile or based on the middle point of the base is how to go about doing this... even though it's already been figured out :]
This is the one true way to solve it. Everything else is just mental masturbation.
If you want to support altitude, just offset the base point vertically (and sort it by the same rule).
Do not draw by walking the tiles in order. This will never work.
In a larger sense, this is an implementation of the painter's algorithm, which will break down if you have large/oddly shaped objects. Just don't do that. If you really do have something like a line, clip it along tile boundaries and sort the pieces. Or you can do an exact sort by treating everything as planes and then clipping the line against them. But you could probably fake it and save yourself the trouble.
At a certain point you just have to give up and go with a z-buffer. But Diablo got pretty far with these limitations, so I bet you can, too.