Ok I managed to figure this out on my own, but I wanted to post the steps here for posterity because there was zero documentation on this (that I could find) and it was practically guess and check.
After I set "Domain *" as described above, it would sign it like this:
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=clientdomain.com;
s=main; t=1250005729;
bh=twleuNpYDuUTZQ/ur9Y2wxCprI0RpF4+LlFYMG81xwE=;
h=Date:From:To:Message-Id:Subject:Mime-Version:Content-Type;
b=kohI7XnLlw/uG4XMJoloc4m9zC13g48+Av5w5z7CVE0u3NxsfEqwfDriapn7s7Upi
31F3k8PDT+eF57gOu2riXaOi53bH3Fn/+j0xCgJf8QpRVfk397w4nUWP/y8tz4jfRx
GhH21iYo05umP0XflHNglpyEX02bssscu2VzXwMc=
notice the "d=clientdomain.com". It was generating this based on the from address in the email, where the from address was something like "contact@clientdomain.com". Obviously if it checked the client's domain and not mine no DNS TXT record was there and the verification would fail.
So anyway I found out in this documentaion that you can set a KeyList parameter.
http://manpages.ubuntu.com/manpages/hardy/man5/dkim-filter.conf.5.html
It didn't really describe what I wanted to do, but I figured I'd play with it. I commented out KeyFile and set KeyList to "/etc/mail/dkim_domains.key" which is an arbitrary file name I made up.
I then created that file and put this in it "*:feedmailpro.com:/etc/mail/dkim.key".
This tells it for any client domain, sign it with my domain (feedmailpro.com), and use the dkim.key file.
Restarted DKIM and postfix
sudo /etc/init.d/dkim-filter restart
sudo /etc/init.d/postfix restart
Now this is the key it generated when I sent a test email.
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=feedmailpro.com;
s=dkim.key; t=1250005729;
bh=twleuNpYDuUTZQ/ur9Y2wxCprI0RpF4+LlFYMG81xwE=;
h=Date:From:To:Message-Id:Subject:Mime-Version:Content-Type;
b=kohI7XnLlw/uG4XMJoloc4m9zC13g48+Av5w5z7CVE0u3NxsfEqwfDriapn7s7Upi
31F3k8PDT+eF57gOu2riXaOi53bH3Fn/+j0xCgJf8QpRVfk397w4nUWP/y8tz4jfRx
GhH21iYo05umP0XflHNglpyEX02bssscu2VzXwMc=
Improvement, you see the d= now is set to my domain (even though the from address of the email was not my domain). However s= got changed to "dkim.key" instead of the selector I chose in dkim-filter.conf. In the original setup instructions I'd set the selector to "mail". That was weird, but I noticed it changed it to the filename of my key, dkim.key.
So I went and renamed "/etc/mail/dkim.key" to "/etc/mail/mail". Also updated the reference to it in "/etc/mail/dkim_domains.key".
Restart dkim-filter and postfix again same as above, and now it started working. Here is the final header which signs correctly using the right selector (apparently based off the filename of the key).
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=feedmailpro.com;
s=mail; t=1250006218;
bh=tBguOuDhBDlhv0m4KF66LG10V/8ijLcAKZ4JbjpLXFM=;
h=Date:From:To:Message-Id:Subject:Mime-Version:Content-Type;
b=c9eqvd+CY86BJDUItWVVRvI3nibfEDORZbye+sD1PVltrcSBOiLZAxF3Y/4mP6vRX
MUUNCC004oIH1u7FYafgF32lpuioMP1cd7bi6x3AZ5zH4BYETNBnnz4AhAPBtqlIh/
FFMz8jkhhLhcM2hDpwJkuKjAe3LzfNVDP8kD11ZI=
Now s=mail is right, and d=feedmailpro.com is right. It works!
Overall this was way harder than I expected and there seemed to be zero documentation on how to do this (signing for all outgoing domains), but I guess it's open source software so I can't complain.
One final note, to check if the TXT DNS record was setup correctly you can do a command like with your domain
dig mail._domainkey.feedmailpro.com TXT
May need to install dig (sudo apt-get install dig). If you're using Slicehost manager to add the DNS entry, you'd enter the TXT record like this.
Type: TXT
Name: mail._domainkey
Data: k=rsa; t=s; p=M5GfMA0...YOUR LONG KEY...fIDAQAB
TTL seconds: 86400
I don't really understand why the name is set to "mail._domainkey" without a period on the end or without my domain, like "mail._domainkey.feedmailpro.com". But whatever, it seems to work so I'm happy.
If you're trying to duplicate this, here are the instructions I started with:
https://help.ubuntu.com/community/Postfix/DKIM
The following is based off of the IP I see in your logs as the mail sending IP of 67.55.9.182.
You have a PTR entry, which is good.
;; ANSWER SECTION:
182.9.55.67.in-addr.arpa. 14400 IN PTR dsl-67-55-9-182.acanac.net.
However your forward and reverse should match ideally. The reverse entry leads me to believe that you are running this off of a DSL ISP connection. That is enough to get your mail marked as spam in some systems. They do not like seeing mail coming from "home" or "consumer" connections.
Your IP is also listed in several blacklists:
67.55.9.182 is listed in dnsbl-3.uceprotect.net
67.55.9.182 is listed in bl.spamcannibal.org
This will also result in your mail being sent to the spam bin.
Resolve the above issues and you will likely see your mail being accepted as ham. Hope that helps and let me know if you have any questions.
Best Answer
You could give this package a try instead: libmail-dkim-perl
One of the walk-throughs linked in the Spamassassin documentation points out a hint that I would recommend to follow:
"You should NEVER need to use CPAN on a RPM or DEB based Linux distribution."