Hi, I'm at a customer who has SJDS running with replication in a large enterprise (not quite as yours but big enough). No real problems at all, quite easy to maintain (if you have fully understand LDAP) including replication and failover. On top, you can get professional support if you like (and really need), call Sun for prices. System is running on a T1000 like a charm (load << 0.1).
If you want to test - just do so, it's free ;-) Cheers and just my 2 cents, Jan