I build mine in a similar manner, but instead of the suckerfish script I use PeterNed's "Whatever:hover" for the IE6- support.
(horrible website, great script!)
I do this because I often need hover effects on more than just the menu, and that script takes most of the headaches out of it. Just design for modern, and then throw csshover3.htc at it. (and before anyone *****es about the 'problems' with HTC's, the ONLY problem is mime-type at which point fix your **** server instead of blaming .htc's)
Though as per others, I include the markup for it (and all the other static elements that are the same on every page) using a SSI... These days that means PHP.
If you're putting your entire sitemap into the menu, your navigation likely ends up such a convoluted mess it's unusable. That's the problem with dropdown menus and why increasingly I'm avoiding using them in the first place and just going for classic drill-down. As a rule of thumb I now NEVER do third-level cascades given what a pain in the ass they are to navigate.