The problem stems from rewriting of headers and its discussed here: https://serverfault.com/questions/442180/sendmail-rewriting-headers-after-opendkim-signature
One of the suggested solutions is to set the correct headers in PHP so that sendmail is given the correct domain information and no rewriting is involved.
In my case, I realized that meant setting $_SERVER['SERVER_NAME'] is the right thing to do as an easy fix. I had mentioned it didn't work for me because I thought Sendmail was ignoring the value. But I tried it again and noticed Sendmail DOES recognize the value from $_SERVER['SERVER_NAME']. The problem I didn't realize before was that I had DKIM Filter configured incorrectly.
In dkim-filter.conf, I had the line: Domain *.mydomain.com
When Sendmail was receiving "mydomain.com" in the header information and calling DKIM-Milter, DKIM was unable to find a match because "mydomain.com" evidentally doesn't match *.mydomain.com. I changed *.mydomain.com to mydomain.com and everything started working.
So all I have to do on all my sites is set $_SERVER['SERVER_NAME'] = 'mydomain.com' before calling mail() or wp_mail() (For WordPress). Everything works then.