Quintin:
Do you reach your server's conntrack limit?
The word conntrack never appears in my logs, so I don't think it's that. The ISP also requires this from tor exits: net.netfilter.nf_conntrack_max = 10000
How many conntrack entries do you actually have when you get sendto failed: Operation not permitted log entries?
sysctl net.netfilter.nf_conntrack_count or cat /proc/sys/net/netfilter/nf_conntrack_count
Regardless of whether this is the root-cause or not, nf_conntrack_max = 10k is probably to low for an exit relay.
If nf_conntrack_count is near nf_conntrack_max, does the problem go away when you temporarily increase nf_conntrack_max?