On second thoughts, it might be possible to use media-specific stylesheets. Only rather than actually being media specific, make them page width specific. So what you would need to do is:
Define the min and max page widths you are going to support, e.g. min width 480px, max width 1200px.
Within that range, identify the widths at which the display breaks down. That defines the display ranges you need to support.
Define the default range and use "media specific" stylesheets to suit the remaining ranges.
E.g. Say that the ranges you need to support are 480px - 639px, 640px - 959px and 960px - 1200px.
Assuming that the default width is 640px to 959px, the following meta commands would define the width-specific stylesheets:
<link rel="stylesheet" href="small.css" media="max-width:639px" title="styles" type="text/css">
<link rel="stylesheet" href="large.css" media="min-width:960px" title="styles" type="text/css">
The sylesheets "small.css" and "large.css" would redefine the menu, (and whatever else needed redefining) to suit the page width.
Note: This solution will not work fully with IE8 and below, as they ignore media specific stylesheets. So one of the ranges must be the default, and IE8 will use that stylesheet. I.e. The default range is set to whichever works best on IE8.
This might be worth considering???