The meny system can't do that
The Drupal menu system does not support what you want to do. Each entry has exactly one parent (which is id -1 if at the top).
The taxonomy module however, can
One could map the menu structure onto a vocabulary tree. The complex part here will be the node <=> term mapping, as I'm not aware of a module for that.
However, it's also worth noting that given that nodes and terms are very similar in D7, it's entirely possible to just migrate to using Terms for your main content, if the multiple parents hierachy generally makes sense for you. This could avoid a lot complexity.
One also make something completely custom or build the hierachy directly onto the entities with entity references, or separately as relations.
If there is a module that solves your problem, you should probably be using it. Since Node hierachy is apparently one such option, it's worth your attention. If it really is buggy, you may want to consider helping out with that, if it helps to avoid a large custom effort.