I’ve tried all of the above suggestions which did not provide a consistent fix. But this does.
On the client only, you may hijack the unused /etc/rc.server bash hook, eg single user boot:
bash-3.2# mount -uw /
bash-3.2# /usr/bin/nano /etc/rc.server
#!/bin/sh
/bin/echo BootCacheKludge
/usr/sbin/BootCacheControl jettison
/bin/echo BootCacheKludge
/usr/sbin/BootCacheControl jettison
Boots are now completing %100 of the time.
Edit: We are now beta testing this workaround on ~50 machines.
Enjoy!