Some companies have a lot of sites covering various topics, for example, http://ninemsn.com.au/
The "100 links per page" is a very old rule back from the days when crawling web pages was much less sophisticated then it is now. Search engines have the ability to crawl hundreds of pages.
The example you are using is a site with a DA of 85 and is in the top 1000 most trafficked sites in the world. This site can support the crawling of 100s of links. Unless your site has an exceptionally high DA, you probably want to reduce your links to the minimal amount necessary to ensure a quality user experience. As you examine your links, determine which links are actually used. There are tools such as CrazyEgg that can help you evaluate your site.
Imagine a site with 1000 pages and a link to all 1000 pages from the navigation bar. What you are telling search engines and users is that all 1000 pages are equally important. That probably is not the case. The most important pages and categories should have a link, but the lesser pages would require an additional click.
Should these headers be implemented in javascript?
Search engines can crawl most javascript. The best practice would be to reduce the links as mentioned above. Search engines reward sites which improve the user experience by providing higher rankings. If you offer 200 links and 150 of them are not used, you are bleeding PR and your site will not rank as well overall, which is by design.
I'd prefer to reduce the number of links, but sometimes company policies don't allow this.
Your role as a SEO is to educate the company on the importance of the changes you recommend. If a company refuses to implement your recommendations, then there is not much you can do about it.