Trying to set up a catch all e-mail in Exchange 2010

We're looking to set up an e-mail sub-domain for a project, and we need to set up a catch-all e-mail address, so whether people send project updates to project1234, or project4321, it will redirect to the one existing e-mail account.

• I've set up the sub-domain MX in our public DNS.
• I've set up the sub-domain in EMC, per this article. We do not have an edge transport server, but the same settings are under Hub Transport, which I thought would be the same.
• I've set up the catch all e-mail address per this article.

The sub-domain works when I send directly to the one existing account with an e-mail address in the sub-domain, and it works if I set up specific aliases on the account, but it's not working as a catch all. When I test from my Gmail to a non-existent address on the sub-domain, it is rejected as an unrecognized recipient.

At first I considered that it might be our spam filter (McAfee hosted) blocking these messages. But when I added an alias in Exchange and did not set up the user in McAfee, it still came through, so it really appears to be something misconfigured or missing in Exchange.

I set up the Transport rule to be "when a recipient's address matches '@sub.example.com$' copy the message to 'existingAccount@sub.example.com'"

I've also tried "when a recipient's address contains specific words 'sub.example.com'" and any other variation I could think of to get a generic catch all for the sub-domain… nothing has worked so far, except creating an alias (which would defeat the purpose of having a catch all).

Does anyone have experience with setting one of these up, and so could provide direction on what I'm missing?

P.S. the NDR

Diagnostic information for administrators:

Generating server: example.com

new@sub.example.com
 #550 5.1.1 RESOLVER.ADR.RecipNotFound; not found ##

Original message headers:
Received: from p01c12m115.mxlogic.net (208.65.145.247) by
 server.local.example.com (192.168.1.18) with Microsoft SMTP Server
 (TLS) id 14.0.722.0; Tue, 9 Aug 2011 11:54:09 -0400

Received: from unknown [74.125.82.170] (EHLO mail-wy0-f170.google.com)  by
 p01c12m115.mxlogic.net(mxl_mta-6.10.0-2) over TLS secured channel  with ESMTP
 id f18514e4.0.181220.00-2292.264602.p01c12m115.mxlogic.net (envelope-from
 <me@gmail.com>);   Tue, 09 Aug 2011 09:54:08 -0600 (MDT)

Received: by wyf23 with SMTP id 23so97339wyf.29        for
 <new@sub.example.com>; Tue, 09 Aug 2011 08:54:06 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        h=mime-version:date:message-id:subject:from:to:content-type;
        bh=+ku4XfmMdO3N03t8z+YI9ApzoPFBdZazI1GqwxB5JPs=;
        b=fkzsd9eyTJown62n8alAINYW6arHT/qB6EjoAzlwoDjRvDpgJERLEGVrw3eXwbJDlU
         aekvxsWTfizZJGxY4KypkJH1T0tnMCjANscAM3avwld8qVbaGlnxE1wipi3i3Bfgcv1R
         l3GNqUqCd0FJIXC02+A2CDkihdxqPM3UKHfwc=
MIME-Version: 1.0

Received: by 10.216.67.8 with SMTP id i8mr1726607wed.61.1312905246774; Tue, 09
 Aug 2011 08:54:06 -0700 (PDT)

Received: by 10.216.210.134 with HTTP; Tue, 9 Aug 2011 08:54:06 -0700 (PDT)
Date: Tue, 9 Aug 2011 11:54:06 -0400
Message-ID: <CAE=Hmibpw4TVZ5MnG81qBjrUdPRc93eNhx8ACD71u4rjKo7evw@mail.gmail.com>
Subject: test test test
From: Me <me@gmail.com>
To: <new@sub.example.com>
Content-Type: multipart/alternative; boundary="000e0ce0cf08db956b04aa149235"
X-Spam: [F=0.2000000000; B=0.500(0); spf=0.500; STSI=0.500(0); STSM=0.500(0); CM=0.500; MH=0.500(2011080922); S=0.200(2010122901); SC=none]
X-MAIL-FROM: <me@gmail.com>
X-SOURCE-IP: [74.125.82.170]
X-AnalysisOut: [v=1.0 c=1 a=nDghuxUhq_wA:10 a=BLceEmwcHowA:10 a=nS36O97Bj3]
X-AnalysisOut: [wUElCrIrAA:9 a=wPNLvfGTeEIA:10]
Return-Path: me@gmail.com

Received-SPF: Neutral (server.local.example.com: 208.65.145.247 is
 neither permitted nor denied by domain of me@gmail.com)

Final-Recipient: rfc822;new@sub.example.com
Action: failed
Status: 5.1.1
Diagnostic-Code: smtp;550 5.1.1 RESOLVER.ADR.RecipNotFound; not found