sprites - Algorithm for spreading labels in a visually appealing and intuitive way

Short version

Is there a design pattern for distributing vehicle labels in a non-overlapping fashion, placing them as close as possible to the vehicle they refer to? If not, is any of the method I suggest viable? How would you implement this yourself?

Extended version

In the game I'm writing I have a bird-eye vision of my airborne vehicles. I also have next to each of the vehicles a small label with key-data about the vehicle. This is an actual screenshot:

Now, since the vehicles could be flying at different altitudes, their icons could overlap. However I would like to never have their labels overlapping (or a label from vehicle 'A' overlap the icon of vehicle 'B').

Currently, I can detect collisions between sprites and I simply push away the offending label in a direction opposite to the otherwise-overlapped sprite. This works in most situations, but when the airspace get crowded, the label can get pushed very far away from its vehicle, even if there was an alternate "smarter" alternative. For example I get:

  B - label
A -----------label
  C - label

where it would be better (= label closer to the vehicle) to get:

          B - label
label - A
          C - label

EDIT: It also has to be considered that beside the overlapping vehicles case, there might be other configurations in which vehicles'labels could overlap (the ASCII-art examples show for example three very close vehicles in which the label of A would overlap the icon of B and C).

I have two ideas on how to improve the present situation, but before spending time implementing them, I thought to turn to the community for advice (after all it seems like a "common enough problem" that a design pattern for it could exist).

For what it's worth, here's the two ideas I was thinking to:

Slot-isation of label space

In this scenario I would divide all the screen into "slots" for the labels. Then, each vehicle would always have its label placed in the closest empty one (empty = no other sprites at that location.

Spiralling search

From the location of the vehicle on the screen, I would try to place the label at increasing angles and then at increasing radiuses, until a non-overlapping location is found. Something down the line of:

try 0°, 10px
try 10°, 10px
try 20°, 10px
...

try 350°, 10px
try 0°, 20px
try 10°, 20px
...

Answer

After some thought, I finally decided to implement the spiralling search method I briefly described in the original question.

The rationale is that the Byte56's method needs special treatment for certain conditions, while the spiralling search doesn't, and it codes in a really compact way. Also, the spriralling search emphasise finding the closer spot to the vehicle to place the label, which IMO is the main factor in making the map readable.

However please continue to upvote his answer, as it's not only useful, it's also very well written!

Here's a screenshot of the result achieved with the spiralling code:

And here's the code which - although not self-contained - it gives an idea on how simple is the implementation:

def place_tags(self):
    for tag in self.tags:
        start_angle = tag.angle
        while not tag.place() or is_colliding(tag):  #See note n.1
            tag.angle = (tag.angle + angle_step) % 360
            if tag.angle == start_angle:
                tag.radius += radius_step
        tag.connector.update()                       #See note n.2

Note 1 - tag.place() returns True if the tag is entirely on the visible area of the screen/radar. So that line reads like "keep on looping if the tag is outside the radar or it overlaps something else..."

Note 2 - tag.connector.update is the method that draw the line connecting the aeroplane icon to the label/tag with the text information.