I have looked all over for this option, but the only mention I see of the max menu width is in the documentation, where it talks about min/max menu width being set by the theme designer. Is there a way to set the max size so that submenu items won't be truncated when they have long name?

Yes there is, but it's a skinner's setting because the menu bitmaps must allow for this, or bitmaps will end up being stretched where they shouldn't with ugly results.

Open NextSTART Preferences, go to Appearence Preferences and click on the 'Menu Buttons' button. Check out the Button Metrics section in the dialog that pops up.