I think probably Javascript is the 'cleanest' solution in this case, but depending on the complexity of your UI another non-JS approach is to make every link target the topmost frome (e.g., target="_top") and redraw all frames in the frameset on each 'click'. This way you know that all frames reflect the latest situation, but it can be annoying to see the whole browser redraw every time you do anything. However, if your browser doesn't *do* Javascript.... (so long as it does do frames.... hmm.. how likely is that?) then it would at least work....
There' s always the possibility that people disable javascript - and checking for instance http://www.guninski.com/browsers.html I would say they have reason to do so. My take is that one should at least provide a non-javascript alternative to browse the site. This also helps with search-engines.... cheers, oliver