You know you're not the only one.. I've been working with DNN for nearly 3 years, and the menu has been without doubt the biggest challenge.
Part of the problems we have are two fold - we have newcomers to DNN who's expectations of what a menu should and could do is influenced by the thousands of different navigational designs on websites around the world. However, the one thing that most people forget is thereare very few menus that are driven by database managed sites and offer the end user the scope of customisation that is possible with DNN.
Then we have issues on compatbility - this is a very subjective topic since DNN seems to cop alot of flack about being completely compliant in the eyes of many. And I agree, yes there are challenges, but it's not all DNN that is the problem, it is in fact shortcomings in the 1.1. framework, on which DNN runs. And yes, I've seen some people make *compliant* skins but they aren't what I feel commercially usable since they limite the designer dramatically.
Having said that - I'm currently writing a book - DotNetNuke Skinning and Design for Wrox similar to the DotNetNuke books around now - the red ones you see. It's forced me to really look at how the menu functions, behaves, can be modified and changed, it's limitations, comparisons between different menus, including third party ones.
I have created for free download, several different skins that have menus on them that have some form of customisation. I don't do too many changes to the menu, since these skins don't get supported like commerical work, hence I can't stray too far from the standards.
You can download them for free on my site and open up the files and have a look at how they work.
I do feel for every person struggling with the menu, you're not alone, but I an also say there are some new things on the horizon to assist you.
http://www.telerik.com and http://www.componentart.com and http://www.devmansion.com have got menus that I know there are DNN providers for. If you want to write one then that would be cool, since there's always room for more.
Nina Meiers