Needs a NONE selector

If you mean the select list within the product node? You could always select just one product, and then ctrl-click it to remove your selection. That would work.

But perhaps making the first option "None" would be a good choice. (That way you can choose to override the Upsell block on a per-product basis, if you wish..)

I would recommend using the http://drupal.org/project/betterselect module. It converts all multi-valued select lists into scrollable checkboxes, and dispenses with the "control click" nuisance on all forms. IHMO, this is probably a "by design" since it's more of a form API issue that's endemic to all Drupal forms.

My idea for the 2.x version is to make it instead an AJAX-ified node select field. So, in the case where you're not allowing for an automatic Upsell block, you can at least start typing node titles and get some results.

The problem would still exist, IMO, with Better Select module because if a user has 1000s of nodes, it will still take some time for all those nodes to be listed on that page. Keeping them in the form of a nodereference callback is probably the best way to go. Thoughts?

I used the suggestion from comment #1 and used the String Overrides module (already was using it for other things) to change the help text under the selection list as follows:

Original:
Select related products to offer at checkout.

Replacement:
Select related products to offer at checkout. CTRL-click or CMD-click to add or remove a single item.

No, it actually does need a NONE selector because by default if none are selected then all products are considered related. I have a product I want no upsell offerings for. My other products I want to keep offering upsell items.

+1 for a NONE option

I do not want random products displayed, only the products I select for each product. Some items may have 3 related items, others might have 6. For the item with 3 related items, I only want the three to show, and not an additional random 3 products as well...