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
You can use the same key for multiple domains. Using different selectors for the same key won't help your reputation. It will also make signing more difficult. You can use the same selector for different keys as they will be published under different domains.
You will need to publish the selector DNS record for each sending domain. Sign the outgoing message with the matching private key.
In my experience, a high percentage of organizations either don't publish a DKIM record. Others publish an invalid record. Neither case adds credibility.
If you are sending from the same IP address, all domains will be marked as spam. Most blacklists are IP based, not domain based. As long as you are using a properly configured server, including DNS configuration it is unlikely your server will be flagged as spamming unless you send spam. Double opt-in should prevent that.
Do ensure your servers are not open relays. Open relays do get flagged and are commonly used to send spam. I do my best to ensure the spam gets left on the open relay as long as possible.
Best Answer
Take a look at this person's question and answer:
DKIM sign outgoing mail from any domain with postfix and ubuntu
DKIM sign outgoing mail from any domain (with Postfix and Ubuntu)
You may also need to read this (especially if you're on Ubuntu)
https://help.ubuntu.com/community/Postfix/DKIM
You'll still need to poke around a bit to see what configurations are relevant to you, but hopefully this will put you on the right track.