Well, when you comes right down to it, you're want frames without using frames.
I'd go ahead and reload the whole page, it's not going to hurt that much: if there are images they'll be cached, and it'll make it much easier to tweak the menu on a subarea-by-subarea basis (and that might be a good idea, if the menu really is that long).
PHP will help in that the menu HTML can go in a seperate file and included as necessary (okay, servers can do this, but PHP can be more flexible about it, such as the tweaking I mentioned).
If you went the Javascript route, you'd find that you'd have to load every single page into the browser in one almighty wallop, so that the Javascript could display it when its link is followed.