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
Best Answer
Are you sure you're after sender_dependent_default_transport_maps, and not sender_dependent_relayhost_maps? In either case, I'm pretty sure the format is like any of the other _maps tables:
The first being an exact sender match, the second being a domain level match.
That being said, I'm pretty sure Google isn't going to allow you to relay through them without authenticating, and as you're handling relaying for multiple users, I'm sure you don't want to setup that kind of relaying setup, nor will they likely want to disclose their passwords to you.