It looks like there are some great libraries out there to do DomainKeys signing of emails on C#/.NET, but I'm having a really hard time finding the same kind of support for PHP. Maybe I'm not looking in the right place?
The only one I found is http://php-dkim.sourceforge.net/; it looks incredibly hacky and supports PHP4 only. Considering how popular PHP is, and how critical DomainKeys are for email classification as non-spam, I'd expect better tools; do you know of any? Any other tricks you'd recommend?
Extra info: I'm using an external SMTP provider because I need to send out thousands of emails per day.
I'd recommend DKIM support at the MTA level so all your server generated email for a given domain is signed by default. (unless you have a really good reason to not sign all server generated email for a domain).
The best starting point in my googling to get DKIM setup on LAMP with dkim-milter and sendmail (on CentOS 5.2 in my case) was Jeff Atwood's post about sending emails through code.
I would agree with him that the first 2 things you should address are reverse PTR record and DKIM signing.
Also very important:
Here is the email ip address blacklist checker that I used.
Those 5 things will solve perhaps 95% of your email deliverability issues.
This Guide for Fedora/dkim-milter/postfix is also very good.
The PHP mail library I use for my app is PHPMailer 5.1 which has DKIM support (and is PHP 5 only), but after doing the research, I decided implementing at the sendmail level was a better solution. As you can see, even the author of PHPMailer 5.1 does not suggest DKIM at the PHP mail library level is the best solution http://dkim.worxware.com/.
Best of luck to you.