Can you pin down..which component is causing the issue by removing the component one by one rebooting and then testing.
Most Probably it should be NTP but still can you confirm. 

1) Is the SEP install a part of the image or installed after the deployment is done?
2) Not every rule is logged by default. Create a new package for logging the rules and export it or you can export and import a sar file into the client.

I still haven't been able to get machines with SEP (installed with NTP) automatically added to the domain.

I know we had this issues with older versions of SAV and found this KB.

http://service1.symantec.com/SUPPORT/ent-security.nsf/docid/2006060208393848?Open&docid=2004052710203048&nsf=ent-security.nsf&view=docid

Surely I can't be the only one with SEP installed that does Sysprep/riprep?

I found a post from about a year ago. I contacted the author, he said he was never able to get it to work.
https://www-secure.symantec.com/connect/forums/os-image-deployment-and-auto-joining-domain-woes

I think it might be because all network connections are set to be blocked until SEP/NTP is fully up-and-running.  The domain join process will occur before that.  You might want to disable NTP in the RIPPREP image and then let the SEPM policies turn it back on.

I do have the option "block all traffic until the firewall starts and after the fireweall stops" checked.
but I also have the "allow initial DHCP and NetBIOS traffic" checked.

I thought netbios traffic is used when a domainjoin occurs?

Hmm, I'd give it a shot with the option "block all traffic until the firewall starts and after the fireweall stops" disabled to see if that helps.  I happend to be able to speak with one of our AD admins here, but the machine will need DNS (53) and RPC (445) for sure to be able to join.  NetBIOS is a different depending on who you ask.

If it does, I'd maybe have a temporary policy for machines as they are imaged and then move them to a new policy once they're going--assuming your're using a SEPM server.