I've generated diagrams from various sources of data in AWS (security groups, EC2 instances w/ their attached security groups, edges between, etc) and never run into this issue. I'm talking thousands to tens of thousands of nodes and tens of thousands of edges.
The utility of these diagrams was limited, given how dense they were. I'm curious what use case graphviz chokes on that would generate legible graphs..
edit: this reminds me that it would be useful for the AWS APIs to return a "modification epoch" number inside API responses, so that while you're enumerating/describing thousands upon thousands of resources, you could at least keep track of whether there have been any modifications between your first and your last Describe* call.
None of these tools are actually appropriate for the job, just never get the time to build something better.
One of the things I rarely see in other graphing tools is the concept of node clusters. Super helpful in a bunch of situations I've encountered and wish it was more broadly implemented in other layout engines.