How can I justify labels when plotting "with labels" in Gnuplot?

I cannot test your particular example, but I have mine that looked like:

...
plot "test.dat" using ..., \
"" using ($1-100000):2:3 with labels rotate left notitle
...

... where the "rotate left" part was taken from the OP.

Well, I didn't have much luck finding info about "alignment" or "justification" of labels on the net; so I tried to look in the online gnuplot help. Basically, the relevant stuff is under help set label - I'm not sure exactly how I got down to it, but here is my command log below;

$ gnuplot
...
    G N U P L O T
    Version 4.4 patchlevel 2
...

Terminal type set to 'wxt'
gnuplot> help with labels
Sorry, no help for 'with labels'
gnuplot> help with 
 Functions and data may be displayed in one of a large number of styles.
 The `with` keyword provides the means of selection.

 Syntax:
       with  { {linestyle | ls }
...
where  is one of

      lines        dots       steps     errorbars     xerrorbar    xyerrorlines
      points       impulses   fsteps    errorlines    xerrorlines  yerrorbars
      linespoints  labels  ...
...
gnuplot> help labels
 The `labels` style reads coordinates and text from a data file and places
 the text string at the corresponding 2D or 3D position.  3 or 4 input columns
 of basic data are required.  ....

      3 columns:  x  y  string    # 2D version
...
 See also `datastrings`, `set style data`.

gnuplot> help set label
 Arbitrary labels can be placed on the plot using the `set label` command.

 Syntax:
       set label {} {""} {at }
                 {left | center | right}
                 {norotate | rotate {by }}
                 ...
 By default, the text is placed flush left against the point x,y,z.  To adjust
 the way the label is positioned with respect to the point x,y,z, add the
 justification parameter, which may be `left`, `right` or `center`,
 indicating that the point is to be at the left, right or center of the text.
 Labels outside the plotted boundaries are permitted but may interfere with
 axis labels or other text.

 If `rotate` is given, the label is written vertically (if the terminal can do
 so, of course).  If `rotate by ` is given, conforming terminals will
 try to write the text at the specified angle; non-conforming terminals will
 treat this as vertical text.

The relevant parts are bolded; and they explain one misconception I had - seeing the rotate left in the OP example, I thought left is attribute of rotate, however it isn't - left is a separate justification parameter, while rotate is a separate rotation keyword (i.e. rotate left doesn't mean "rotate counterclockwise 90 degrees" as I initially thought).

If that is so, one can then invert those two keywords:

...
plot "test.dat" using ..., \
"" using ($1-100000):2:3 with labels left rotate notitle
...

... and get the exact same output plot. And if finally we replace left with right, as in:

...
plot "test.dat" using ..., \
"" using ($1-100000):2:3 with labels right rotate notitle
...

... we can see that the label is still rotated "left" (counterclockwise 90 degrees) - however, it is now right-aligned to the position.

Well, hope this helps,
Cheers!