I think there should be extra parameters for wp_nav_menu() to let theme developers insert extra li items. Sometimes I want an extra li at the begining and/or end of the menu to add images for rounded corners*, or an extra li in between each item for a separator image.
It should also be possible to assign an image to each menu item, instead of just using text.
* - Please don't say to just do this with CSS. It isn't supported by IE6, 7 or 8, so that's just not practical yet.