"Sitemaps and site indexes are forms of supplemental navigation. They give users a way to navigate a site without having to use the global navigation. By providing a way to visualize and understand the layout and structure of the site, a sitemap can help a lost or confused user find her way. Sitemaps are more widely implemented than site indexes, but both have their place and fulfill a unique information need."
For some reason (not really backed up back facts or research) I had ditched sitemaps as a rather bad idea. Might be time to revisit the issue more seriously in light of this article.