I was leading the AppKit group at NeXT at the time, and "NS" definitely came before the Sun relationship, referring to NextStep (or NeXTSTEP, the spelling changed every release). I distinctly remember our team expecting we'd have to suck it up and change the prefix to something more neutral when the Sun deal was made, and then being surprised that they didn't seem to care when the spec was discussed. Maybe the alternate interpretation of "NeXT and Sun" satisfied them, but I don't remember that expression ever being commonly used, and it was not the original basis for NS.