I'm not sure but there are always better ways to do things, always!
A-Z pages? 20-500 links on each page?
Sounds like a laundry list. ;) Not on every page but on the second level of pages that may count. More than 100 links on a page would be a concern for me from a "usability" standpoint. More than 300+ links I think is the Kiss of Death for many sites. As a user, I surely don't want to have to wade through a page with a "Laundry List" of 300 or more links and you say you have upwards of 500?! That may not work and may be the reason why you are in your current situation.
As mentioned above, a rebuild of the taxonomy might have been in order back when the symptoms started to appear. You could do it now too if things have not improved, what have you got to lose? And please, don't tell me that there is no other way, there is young man, there is! You must find it. Just because the competitors are doing it that way, doesn't mean that you have to. You can always set the new benchmark and then let them all flounder about while they try and figure out what you've done.
While that addresses part of the challenge, it still leaves that laundry list of links within the "overall" content of the page. I feel that by using absolute positioning of those elements, you can focus the meaning of your content more efficiently by serving the primary content first and then other elements in their respective order. You want the page to degrade gracefully when CSS is off so the ordering of the elements is imperative from a usability standpoint. And of course an indexing one too. ;)
Me too. And it usually isn't. But, when you get into the "Mega Menu" mindset, there may be some challenges there. That's why I feel menus should be dynamic and specific to the category you are in. Top level categories remain visible at all times. Sub level category links only come into play at those levels. If you have 5 categories, you'll have 5 main menus. If you have 50 sub-categories, you may have literally 50 sub-menus depending on the breadth of each category. You build it as they traverse the link path and only serve what is "specific" to that category. Did that make sense? I have to read these over and over to make sure I didn't confuse anyone, myself included. :)