I've made some significant progress since I first posted this. Browsing through the log file again, I finally noticed the following:
@4000000050bfc4180fc8562c spamdyke: DENIED_RDNS_MISSING from: email@example.com
origin_ip: 10.0.0.9 origin_rdns: (unknown) auth: (unknown) encryption: (none) reason: (empty)
This put me on to spamdyke. I was then able to temporarily restore E-mail relaying by disabling the "reject-empty-dns" option. After doing this, most messages worked, but some others were being denied due to not having an MX record. This prompted me to disable the "reject-missing-sender-mx" option.
I don't like just having these options disabled as this leaves me vulnerable to spam from incoming messages. Are there any ways to configure spamdyke to completely bypass the rdns look up and the mx lookup on ip addresses that I specify? There are options in here like "ip-in-rdns-keyword-whitelist-file", but as far as I can tell, that's for whitelisting the result of the rDNS look up after you get it (i.e., considering the message as ham because it comes from a known good sender and bypassing all of the spam checks that come later).
These IPs don't have rDNS entries because they're internal, so I want spamdyke to completely skip looking up the rdns and mx records for them, but only them so that it will continue to look for rDNS and MX if the message came from outside.