Menu Settings in not appering on all node/add/*

This is in fact by design, bacause having menu items both generated by category_menu and manually by the user is problematic. Jaza took care to remove the "menu settings" part through so called "menu wrapper" module in earlier versions, which I later proposed to incorporate right inside category_menu which is cleaner. But either way, the intention was to remove that part of node/add form if category_menu is in use.

As for my opinion, I don't really see what's the problem with category_menu + menu OTF fieldset (or with multiple menu items for a node in general), now that D6 menu system is much more robust than D5 was, but I didn't really check either. BTW I already wanted to remove that fieldset on my site for different reasons (people with administer menu permission used to fill that as a regular part of every single node they submitted, resulting in bloated and unusable menus on the site - my opinion is that menus are for site features or categories, NOT for separate nodes [depends on the use-case, obviously]), and so I didn't mind the removal. Maybe it might be nice to have a setting for that, but I'm unsure whether we already have too may settings from usability point of view.

The dependency between category_display and category_menu is in my opinion by itself unnecessary and problematic (and caused a lot of problems), but as I understand it, it's the result of keeping category module in sync with core, where book module now store it's hierarchy information in form of menu items (which is, again, in my opinion inherently and utterly wrong, but I'm not going to raise any alarm about it, because I wasn't there when they created that bit, and having different opinion on certain matters at Drupal [including the content-items-in-menus issue] is very dangerous, and bound to cause any issue being marked as "won't fix" immediately; that's, sadly, how my experience with this community goes). Anyway, we have what we have, necessary for core compatibility, and that means that category_display doesn't pull data from category tables directly (as it used to in D5), it summarizes menu items generated by category_menu now.

As for your options with current version, I suggest to go with 3) - it's not really nice to hack code (and would need to be re-done on every update), but it's going to cause no other problem (if we want to introduce a setting for this, it's going to do exactly the same). Using outdated versions is a problem, given all the bugfixes recently included. (See #457688: Get rid of Menu wrapper, moving functionality to category_menu for details about that bit of current code.)

I changed this issue to a support request, because otherwise I would be forced to mark it "By design", which I dont't like to do. Feel free to change to a feature request for the setting, if needed, but I can't guarantee much attention to that.

The option to generate menu items is set on a per-container basis, which is not that simple to guess at the stage of a fresh unpopulated node/add form (and even less if the container settings got changed when some posts are already there). Once you have a container accepting this node type, but not required selection, you may not know what the user is going to choose, it's quite unslovable then. Also we're speaking of users with "administer menus" permission, which should be rare on average site (otherwise the menu fieldset is not shown already).

Anyway, to be honest, Category module is in a position (lot of complex code, maintainer short on time, almost no other contributors), that it's difficult to keep it even somehow working. If we managed to fix all existing features in D6 version before D7 is out, I'll call that a big success. There's a LOT of things that may be improved in this module, but no-one to work on that.

Still, I see your post as a feature request. Category package removes that fieldset by design, so any more granular / smarter way to handle it is a new feature. Feel free to implement it yourself, and provide a patch.