Navigation should not be that complicated. Really. If there are links that as you say are non-relevant on some pages, then I would be considering if they should be within the navigation at all. Okay- before you freak out, here is something to consider.
Google and indeed Bing to possibly to a lessor point, play kinda dumb when it comes to navigation as not to tip their hat. But the truth is, they both recognize navigation when they see it and if the navigation links change from page to page, they take notice. Now you are not going to get a slap on the wrist or anything, remember that Google does not always give away it's best secrets, but they will note which links are persistent and which ones are not. The non-persistent navigational links will weigh as much as any link and not as a navigational link. Keep in mind that the most valued links are header navigation and in content links.
When if comes to navigation links, the rule is a simple one. Link your most important topic pages. Simple huh? If you use a drop-down style JavaScript enabled navigational links, then those drop-down links should be the most important sub-topic pages within each topic. Still simple. Here is where it gets hard. Limiting yourself and trusting that you did a good job. One way to know what is important is to look at your site logs, though I caution you a bit, this can be skewed by existing navigation. You want to provide navigation to get people started and not answer all of the needs. Sidebar navigation can help as well as footer based navigation. Sidebar counts quite a bit less for link importance but still noticed as navigation, and footer navigation far less than that. But still, you can put important items in the footer such as about, privacy policy, acceptable use policy, contact, and so on. If you really need more options, your sidebar navigation is your best bet. This allows you to load up links, though I caution you that this is often discounted value the more you put in, and keep your header navigation simple and clean.
It sounds like you are over complicating things a bit and clouding what is really important- creating a useful and concise experience for the user. It should not take too much brain power to create navigation. Seriously. If it feels more natural to you then it will feel more natural to your users too. Remember the K.I.S.S principle. Simplicity is often the best solution. I have to remind myself of this from time to time. We all wander a bit on our ideas. Just pull back on the reigns a bit and you will be fine.
