How did spammer spoof emails with my google apps domain (it even has DKIM!)

I have been getting a lot of bounce-backs lately.

I thought my google apps account has been compromised, but there is no activity on my apps account, and there is certainly no malicious user that I can see.

Since the email is always send from some random username (eg [email protected]), I tried to find a way of disallowing sending email from unregistered users. I couldn't find anything.

What worries me is that the message has a X-Google-DKIM-Signature, and it says "Google tried to deliver your message". Does that mean the emails are originating from my trusted clients? (I only use gmail)

AFAIK spammers are free to spoof every field of the email, but the DKIM should make the (modern) servers drop these unverifiable emails.

Any idea where the leak is?

Here's an example bounce-back:

Delivery to the following recipient failed permanently:

     [email protected]

Technical details of permanent failure: Google tried to deliver your
message, but it was rejected by the server for the recipient domain
174.133.125.2 [174.133.125.2].

The error that the other server returned was: 553 sorry, that domain
isn't in my list of allowed rcpthosts; no valid cert for gatewaying
(#5.7.1)

----- Original message -----

X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=google.com; s=20120113;
        h=x-received:x-received:received-spf:mime-version:date:message-id
         :from:to:subject:content-type:content-transfer-encoding
         :list-unsubscribe:x-gm-message-state;
        bh=l2RiLiEDvrHgBMSAjtLmNgIpmW4D1EFAIr3O42oBysM=;
        b=UBSW90YcP4Fu1vDLnvGCp06XEE5+FOAUR62qSnQrnaPcsKWJSdFT7x7XSU2+vHrpTI
         RaN4pHJWlaMHqtAUoMFE0T9hgBj0blZnNMDtMRFkcU4QD0E/QNw6VIQlAjWGOWvXghMc
         G+SX+YLugnQEWS6tG6guf1hF31XoB4a2HxvxQO4J+lWNLg60LaS7K4DiUr4yG25mvXBU
         uy+tXqjLKyZgA9jmvyVvBKeRYVwMIWvscJ26yw17K7LRfGZkAXzuvTVyGMuLUzthj5c5
         MSNZOG6u5faxtzdBkGRiNQVarq3IsXBuXcxk1vRiUktbM8OIhm2D4IrvhmTPrDF4yyTz
         EHhw==
X-Received: by 10.50.37.239 with SMTP id b15mr4892361igk.69.1360854627245; Thu, 14 Feb 2013 07:10:27 -0800 (PST)
X-Received: by 10.50.37.239 with SMTP id b15mr4892357igk.69.1360854627177; Thu, 14 Feb 2013 07:10:27 -0800 (PST)
Return-Path: <[email protected]>
Received: from [117.201.44.87] ([117.201.34.157]) by mx.google.com with ESMTP id vx6si33676538igb.26.2013.02.14.07.10.25; Thu, 14 Feb 2013 07:10:26 -0800 (PST)
Received-SPF: neutral (google.com: 117.201.34.157 is neither permitted nor denied by best guess record for domain of [email protected]) client-ip=117.201.34.157;
Authentication-Results: mx.google.com; spf=neutral (google.com: 117.201.34.157 is neither permitted nor denied by best guess record for domain of [email protected]) [email protected]
MIME-Version: 1.0
Date: Thu, 14 Feb 2013 20:40:29 +0530
Message-ID: <B23FC935D84FBB6D39DD9BDCC44CD2.176.3699432888759@D>
From: "Valetine's Day" <[email protected]>
To: [email protected]
Subject: I will be excited if you are my Valetine
Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: 8bit
List-Unsubscribe: <mailto:[email protected]>
X-Gm-Message-State: ALoCoQkVcAw4pG/8g2x1C02KHf4lLkBdJ4iLe9r1ZeGlGE1AwtZEQm5VsHh9tNmG04yH2ahWqXnIiKu7DrTf7j6bLHEaF0l0AMhrC6ZvnyJTUr4n+9TKMieQPycP0Pw8sCJ8DELiMNlLI/CGbgQ1ObMLghXauZTeqg==

----- End of message -----

Ensure you don't have catch-all address enabled for your Apps account, otherwise you'll be getting tons of random stuff. http://support.google.com/a/bin/answer.py?hl=en&answer=33962

Don't worry about X-Google-DKIM-Signature (or any other headers prepended with X- in general), this one is Gmail specific and it is not a real DKIM signature for your domain. If you want to set up one, review the following article: http://support.google.com/a/bin/answer.py?hl=en&answer=174124

The rejection is not related to DKIM but to the recipient. But why should Google mail servers try to deliver to wrong MXs? Doesn't make sense to me. The recipient system could be incorrectly configured, of course. Do the failing recipient addresses have the same MX?

Something else: Have you verified the DKIM signature? Maybe it's just some technical looking text...