I have a site with around 8000 domains. I've discussed with Ken Rickard about DA not being designed for that number and it kind of shows. Luckily, issues are solvable.
We have a blogging platform that people can register on and start blogging on. Each user will get their own subdomain being their blog. The system also has a central hub for the platform being the default domain.
Domain User and Domain Alias modules both have the issue of not being very fast when domain count rises above – let's say 1000. The modules implement the domainload hook and do a query per domain – in our case 8000 extra queries per page, 16000 if Domain Alias is enabled.
There is a patch to cache domain_lookups in D7. We used that as an example and created a similar one for Domain User D6, patch attached. Basically when the first domainload hook is triggered, we load all the domain_user data from database and store it in a static array. This means that query count per request for domain user drops from n to 1. The solution however consumes some PHP memory, keep that on mind. Performance-wise it's a lifesaver for us, though.
Do create the same patch for Domain Alias as well when you need one.