Thats exactly what I did with my site maps, put a line of text explaining each link and sneaking in some additional key words.It is ranking very well on Inktomi on dozens of keyword phrases. I will keep you informed how it does on Alta Vista and the other engines.
We decided however to leave the menu off one page, call it a text only menu page, and just listed links to the most popular pages and section indexes with short one line descriptions (with attention to a reasonable number of keywords - the ones that always came up in our AV keyword searches).
That page after 2 months, is now doing exceptionally well. Its pretty devoid of content, but it shows that AV is preety sensitive to keyword weightings and leaving odd around 6 to 8 lines of js lifted the ratings of this page very well.
the navigation was vastly improved and many congratualted us on it. compatable v 4's and up. however we feel the extra code overhead of around 6 to 8 lines at the very top of the HTML on every page reduced our relevancy a lot with AV mainly. (most of the code was on external js files, but it still required these lines to be embedded. All other major SE indexes showed no effect... only AV really
Congratulations on the forum. I am sure I will be spending a lot of time here.