I'm making a wild guess here, but with a bit of luck it may turn out to be right...
I had a similar problem: My menu seemed to work only once in a while. On and off, and no pattern recognizable as to why this would happen. But then the problem went from bad to worse: Not only the menu acted up, but also other links on my site stopped working as they should. I nearly went crazy because I badly needed to do some updates on my site, and it just didn't work. Either the "Edit" link didn't work, or when it did, the "update" link was dead. AARGGGH!
So, I did some testing: "normal" links worked (such as in the Links module, or included in a Text/HTML module. But any link that was rendered as Javascript (includind those in the menu) acted up.
Eventually, I found out the culprit for my problem was a setting in the host settings: I had set the ViewState to be saved on the server memory (because that was supposed to improve the performance), rather than in a hidden field on the page. Now I tried to change the setting, but that didn't work again because again I would have needed to use links that had a javascript attached to them. So I went directly into the database, opened the table HostSettings and changed the value for PageStatePersister from "M" to "P". Worked like a charm, and since then both my menu and all the other javascript-links are working perfectly again!
Hope this helps!