I couldn't have a Tolkien's Middle Earth based map without having The Two Towers (definitely), the Lost Island represents Valar (also needed), The Raiders Haven are the Pirates that haunted Middle Earth and do spice things a bit in the board game.
What time period are you shooting for? The two towers were only truly relevant during the war of the ring, IIRC. Valar and Numenor OTOH weren't important during the war of the ring. And I don't remember pirates being significant in either the Silmarillion, the Hobbit or the Lord of the Rings.
I think you're making a huge misjudgement about how complex the map is, and I strongly belief you need to simplify. If you insist on keeping everything in, perhaps you should make things more uniform.
For example, I think it would be better if you created a "special location" symbol. Place it on the tower of doom, tower of control and the house of gods. All of them function as a simple +1 autodeploy; don't mess around with bombardment or receptacles. This keeps them on the map while also reducing the complexity.
Similary, I think you should uniformize the races that have a symbol on the map. In other words:
The following combinations give a +1 bonus:
- elven town + elven training ground; 
- Human village + warriors training ground; 
- Human village + horsemen training ground; 
- Gorks camp + Gorks training ground; 
- Raiders inn + Raiders training ground; 
- Dark elf village + Dark elf training ground.
That way, even though there are a lot of symbols on the map, most of them work the same. Furthermore, you lose the odd "hold all logoths for a +1" which was different from everything else on the map.
To make the ports more easily understood, you could draw connections between them. For example, Mishyelly (sp? can't read it) connects to Akherat; Akherat connects to Hellnor, Hellnor connects to Tehl. Or you should let all ports connect to each other. They definately should all function the same, rather then Hellnor being different. 
I don't see why the one way attacks from Norhtern Logoth are necessary. Again, they are something not found anywhere else on the map, adding to complexity for little gain. Can't you just make it connect to 1 or 2 territories, just like southern Logoth? 
Also, in a lot of places, you use forests as decoration, but aroung the Logoths you use them as impassables. Perhaps you should remove the decorative forests to reduce the possible confusion with either impassable forests or the Gorks camps?
Finally, I think you make an unneccesary distinction between dwarg gateway entries and dwarf gateways. I think it would be easier to understand as those all functioned teh same: as countries inside countries that are connected to each other. If you do this, you may want to move them to avoid having them connect coutnries that are next to  each other.
Thanks Sync!  The map is nooot that complex... I think that in a second approach people will get the feeling of it. And after all.. Tolkien's world was complex.
I'm affraid players won't take that second approach.When they see a lot of symbols on the map, quite a few will go "that's complex, I'll look for something easier". And quite a lot of those willing to put in the effort of reading the legend, will leave after that because the legend isn't easily understandable either.
The word ORC comes from the latin word Orcus (one of the names of God Pluto – The Lord Of The Underworld). But the meaning that we now give to the word was introduced by Tolkien himself. Therefore to avoid copyright issues we should stick to the word Gorks.
I know that this meaning was introduced by Tolkien. But he isn't the only one to use it. Warcraft, Warhammer, D&D and Magic the Gathering, to name a few of the top of my head, all use orcs. They've become just as staple a part of fantasy as elves and dwarves, IMO.