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
DKIM is about reputation. From the intro paragraph of the main website (dkim.org):
DomainKeys Identified Mail (DKIM) lets an organization take responsibility for a message while it is in transit. The organization is a handler of the message, either as its originator or as an intermediary. Their reputation is the basis for evaluating whether to trust the message for delivery.
One place you can look up reputation is at: http://www.dkim-reputation.org/
Yes, a spammer can DKIM sign a message, but that message then goes through SpamAssassin and gets scored. You then build a database of signed domains and what kind of messages the domains send. If (say) gmail.com keeps sending spam, then SA knows to increases the spamminess level of that domain; if it sends more 'ham', then SA will learn to trust those domains/signatures.
You are correct in saying that you can't base the spam or ham status of a message with DKIM alone (at least not right away), but it helps in determining where a message has passed through. Whereas a non-signed message could have theoretically come from anywhere, having its content changed at any point in the process. Once you have at least one DKIM signature (and there can be several), you have a data point to start assessing the reputation of relays.
DKIM is about taking responsibility for the mail that goes through your relays. If you're not signing messages, then why should receivers bother trusting you? If you do sign messages, then recipient SMTP servers can learning about your relays and be confident on the reputation data they're collecting. They're just one more link in a chain (Bayesian filtering, dial-up/DSL black lists, razor content database, etc.).
For point (1): mailforwarders were thought of in the design of DKIM:
http://www.circleid.com/posts/dkim_for_discussion_lists/
For point (2): you are correct, that you still have do spam checking. But before you had no link between a domain and a spam score: every message was treated independently of every other message. Now, you potentially have something linking different messages together. Put that common link into a database and you can start doing analysis on it.
Best Answer
Incorrect implementation leading to rejected mail is the only pitfall I can think of (or slow DNS propagation causing trouble: Make sure to publish your DNS record with the key a few days before you start sending DKIM-signed mail to avoid that).
If your DomainKeys/DKIM setup is correct I don't think it can cause any problems since if the receiving end doesn't recognize the DKIM header in the email it will just ignore it like any other "noise header".