At first, I tried both versions of the related table - News ID and categories as a list of values separated by a comma.  And multiple news ID records and category ID.  The difference in query time was 0.0002ms, but managing multiple records version was too hard (too much rewriting original code), so I decided on the first version.   

Admin area 

It was a nightmare. You have knowledge about admin UI enough but...  I tried checkboxes, multiple dropdown, comma type... all of them failed on default value.  There is no example how to this, what is needed for it...  When I wanted to give up, when I complained on gitter, it hit me... use method type and write everything yourself. You did more complicated stuff with efiction before. Yes, and it was it.  

When you are editing news, there is new tab News Categories and you can check more than one news category. The primary category has a different value.  It would be nice to react to changing the category on the first tab, but it would be too much.

When you click on the plugin admin page itself, there is a next way how to add multiple categories. It is the list of news with joined categories. When you display this page, it checks if a related record exists, if not, it is generated (e_admin is doing this for you, but classic Admin UI is not - or I don't know how)

Frontend 

1. new URL for the category page

2. new menu for categories with correct numbers of posts

3. content of category page (news listing)

4. displaying  categories on news extended page

New URL for the category page

The easiest part for e_url addon. You just need the correct regex and voila, everything works (just the plugin URLs are called differently than core news ones). 

It is hardcoded for now:

• alias (default news-category) - don't use slash or just news
• Category ID
• Category SEF
• ".html " - Google just likes HTML pages and it solves issues with the last slash in URL (and I can remove one of my customization of news URLs)

New menu for categories with correct numbers of posts

I thought that the custom page code is too complicated. Try to look at the category part of news_handler. Shortcodes are written totally different ways and the option just to replace the shortcode or add a new one for the category URL wasn't possible. So file newscategories_class.php is just a copy of the category part of the news handler.  I tried only extending it, but without success.  I don't how, but it just works. There is nothing wrong, just too advanced code and marked EXPERIMENTAL after so many years.

Content of category page (news listing)

This is a copy of news.php from the plugin folder.  I was afraid to delete something so I just changed the query and pagination links.  Did you know that if you want to list the category, the URL parameter is "list" and not "cat" anymore? The result of studying code is 2 next issues. 

Displaying categories on the news extended page

- there is the shortcode for use in news view template {NEWSCATEGORIES} and there is a way how to replace the original core {NEWSCATEGORY} shortcode without template change in theme shortcodes. HTML markup is hardcoded for now. Short of time. 

The plugin was posted on Github, but you shouldn't use it before the route and the canonical URL is not solved. For now, there is core solution (URL to core category page)

Any feedback is welcomed.

By the way. On next day after first using this site (it was after Saturday midnight), it hit me.  I have fully separated news categories management from the core. No limitation, no waiting for solving issues, features adding...  So yes, this is a big thing. And big thanks to Alex for challenging me in this. No one with a self-preservation instinct should try something like this, really. But I owe him a theme, so I wanted to make it up to him and this is the result. 

AGAIN - it is in development, but prepared for testing and ideas.