Storing additional data with a node reference
Have you looked at CCK3 for Drupal 6? It's not stable yet, but the package does contain the Multigroup module which may be exactly what you need. A 'multi group' is a group of cck fields which can be repeated just like normal multi-value fields can. This means that you can group a node reference field with a text field and repeat that combination as many times as needed.

If you decide to give it a try, I recommend that you create a test site first to check if Multigroup and the rest of CCK3 is stable enough for your use case and to make sure that it doesn't interfere with other modules you need.