I think we need to take care to distinguish between the items displayed in the Table of Contents window, and the items displayed in a Legend Layout Element.
The ArcGIS 10.2 Online Help seems to have blurred over this distinction:
The size of WMS legends can vary greatly. Sometimes the size of the
legend specified by the server is too large to be displayed in the
ArcMap table of contents. This usually happens when the legend for a
layer contains multiple symbols, such as a transportation layer
displaying symbology for the different types of roads. With WMS
services, the legends for layers are transmitted over the Internet as
one image containing all the symbols. Although ArcMap supports legend
entries with multiple symbols in its table of contents, ArcMap expects
these entries to contain multiple images, one image per symbol. ArcMap
also places a limit on the size, height, and width (in pixels) of an
image it will display in the table of contents. When the image
received for a layer in a WMS service exceeds this limit, no legend is
displayed for the layer. These layers are therefore listed in the
table of contents without symbology and without expansion controls.
When a WMS legend is available but is not displayed in the table of
contents, you can view the legend on the Styles tab of the WMS
sublayer's Layer Properties dialog box.
While there are many GUI and ArcPy options to modify the items displayed in a Legend Layout Element, my understanding is that the items displayed in the Table of Contents window are much more "hardwired".
Consequently, as someone more accustomed to authoring non-web maps, I think your only options may be to do things like:
- Reconsider how many layers you draw
- Reconsider whether you need to have multiple categories for as many layers
- Experiment with using Dynamic Legends - I am not sure how ArcGIS for Server handles these.