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.
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.