Node reference - limit so node can only be referenced once
Node reference (for Drupal 6) and Entity Reference (for Drupal 7) fields can be configured to use a View to show the available choices.

So, first create a View that shows all buddies that are not related to a runner. Then configure the field that points to the buddy to use that View. 

To construct that View you may use the Corresponding Node References. It syncs the node reference between two node types which have a nodereference to each other. WIth this module your View only has to list buddies that have no runner related. This module is for Durpal 6 (I'm guessing your are using Drupal 6), but there's a similar one for D7.