Justme, here’s what these mail headers are telling me:
To: dan@mydomain.com
Spammer decides to send message to dan@mydomain.com
From: info@mydomain.com
Spammer knows that he can specify ANYTHING for the From: section of the message, so to prevent dealing with any bounce messages or complaints, he decides to say the message is from info@mydomain.com. This is just the way SMTP works - anybody can forge a sender.
Received: from 130.red-81-34-111.pooles.rima-tde.net (HELO mydomain.com) (81.34.111.130) by unknown.sagonet.net with SMTP; 11 Jul 2005 21:55:56 -0000
This is the part he can’t forge. Spammer using hijacked computer 130.red-81-34-111.pooles.rima-tde.net aka 81.34.111.130 connects to your mail server 63.246.XXX.XX (the IP of mydomain.com) and sends a message to dan@mydomain.com. The (HELO mydomain.com) part says that the spammer identified itself as “mydomain.com”. They could have said anything here, it doesn’t matter. The “by unknown.sagonet.com” means that your server accepted the message - unknown.sagonet.com is the default reverse dns name for IPs at Sago Networks - so this was a result of doing a reverse dns lookup on your IP 63.246.XXX.XX.
Your server says “yes, I handle mail for mydomain.com, I’ll take the message.”
The message was passed on to the mail system, which now has to figure out what to do with a message sent to dan@mydomain.com.
During this process, a “message-ID” is created. The mail system needs this ID to be unique for obvious reasons - so it puts together a combination of the date/time, the process id handling the message, the mail system name (qmail), and the “main” domain that the mail system is configured with. Here’s what it came up with:
Message-ID: <20050711215610.25424.qmail@mymaindomain.com>
I’m fairly certain it’s getting the mymaindomain.com from the /var/qmail/control/me file.
Your server determines, via the catch-all you’ve set up, that it should forward the message on to my_email_at_yahoo@yahoo.com. So it does - it connects to yahoo’s mail server and sends the message on. So in this sense, your server is sending (forwarding) the spam message - but only because it was told to forward mail sent to dan@mydomain.com to your yahoo address.
So, to make a long story short, the spammer could send a message to dan@mydomain.com since your server is set up to accept mail for mydomain.com. And your server forwarded that message on to your yahoo.com account since that’s what the catch-all is set up to do. The end result is the spammer’s message ending up in your yahoo.com inbox.
I hope I’ve answered your question here. I don’t see anything out of the ordinary, no illegal relaying, etc. Everything looks on the up and up - except for the fact that there are spammers in the first place giving us all headaches 
Let me know if you have any questions about this,
Paul