"While OAFS is shiny, its a fucking PITA to setup"
Oh its not that bad. Google spinlocksolutions and AFS. Obviously start following the tutorial with LDAP, then kerberos, then afs... The tutorials are extremely long because of endless screencaps and tests/experiments, the actual work required is pretty minimal. My puppetmaster has a couple files, maybe a screen of manifest instructions, that's about it. It really does make life easy in the long run.
"but if our internal BIND takes a crap, kerberos stops working which breaks OAFS"
That is true, I did end up with a ridiculous amount of replication. Multiple LDAP servers, multiple BIND, etc. If you're in physical world this is cheap/free, but I can totally see in virtual/cloudy world where each virtual machine costs $$$$ and every bit/cycle is accounted for, this is a bit of a scaling/financial issue. Every 24x7 machine I have is a primary for exactly one thing also a secondary for as many other things as I can set up.
The biggest annoyance I have with AFS at home is the eternal battle between cron and AFS (really, kerberos) ... they just don't conceptually get along very well.
Mystery service that doesn't like NAT... let me guess it involves SIP protocol? SIP doesn't like NAT very much. OR let me guess, minecraft.soylentnews.org?
I'll take your word for it. We're still undecided on the filesystem issue, but it looks like IPv6 support still hasn't landed in OAFS, and I rather not reintroduce IPv4 back into our BIND instance. We're going to glue the sysops heads together somepoint this month and discuss it more indepth.
As for cron and kerberos, keytabs are a wonderful thing; we use kerberosized SSH for our cron services so we don't have to deal with SSH authorized_keys madness (we have a backported OpenSSH on the server which can pop a key from LDAP which we use for staff gaining access to the network and for the SSH proxy), but kerberos allows us to have one central list of authentication. We've got master/slave KDCs setup, and BIND is replicated, though we haven't tested failover (yet). LDAP isn't, mostly because slapd is a fucking pig to setup (they threw out a perfectly sane config file for putting everything in LDAP and then poorly documented it to boot!), but all the services are using local accounts so the site itself will stay up if LDAP takes a shit on us.
As for our IPv4 only service, you'll have to wait and see. Trust me, I think you'll approve of this (and I plan to write patches to bring it to IPv6 sooner or later)