You can try the PARTIALS options for MapServer labels. This makes sure that labels are only drawn if they can fit completely on the generated image. It's set to TRUE by default, so try FALSE.
Can text run off the edge of the map? Default is true.
COLOR 150 150 150
There are several other placement options available to experiment with such as REPEATDISTANCE, MAXOVERLAPANGLE, MAXLENGTH and:
Position of the label relative to the labeling point (layers only). “Auto” placement is only available with cached labels.
The auto option for placement is only available for cached labels. To enable this option you the LABELCACHE option must be set to ON for the LAYER object - it is ON by default so you shouldn't have to add this unless yo uwant to be more explicit.
Specifies whether labels should be drawn as the features for this layer
are drawn, or whether they should be
cached and drawn after all layers have
been drawn. Default is on. Label
overlap removal, auto placement etc...
are only available when the label
cache is active.