With a large menu structure (and maybe a custom walker or two) nav menus can take quite a long time to generate, and they will be regenerated on every page.
VIP has a menu caching plugin for WordPress.com that can probably be easily made compatible with WordPress.org installs