Dear Lazyweb: Domain Records Propogation?

[avocado_tom]

Dear Lazyweb,

I recently migrated several of my domains to a new hosting company, as the old one was "going away". I migrated my primary domain, roadtrip dot net, to the new server on 4/29. As of that evening, the whois record had been updated to point at the new dns server and I was receiving some mail there.

On 5/4, the machine that had been previously hosting my domain was shut down. Some (most?) mail to my account is now bouncing, and the headers show that servers are still attempting to deliver my mail to the old machine (see below the cut). I would have expected the MX records to run out prior to 5 days (although I honestly don't know what they were set at). Any ideas on what might be going wrong?

Thnx,
Avo

Status message
Reporting-MTA: dns;tw3.myworkdomain.com

Final-Recipient: rfc822;
Action: FAILED
Status: 5.1.0 (550 5.7.1 ... Relaying denied)
Remote-MTA: dns;mail3.oldhostingmachine.org.

headers
X-Server-Uuid: 1144AF26-CDDF-45AF-8798-E8A84F4A91E4
Date: Mon, 05 May 2008 09:00:20 -0400
From: "Thomas Tarka"
To: tommy@roadtrip.net
Subject: ping
MIME-Version: 1.0
X-TMWD-Spam-Summary: TS=20080505130039; ID=1; SEV=2.3.1;
DFV=B2008050510; IFV=NA; AIF=B2008050510; RPD=5.03.0010; ENG=NA;
RPDID=7374723D303030312E30413039303230342E34383146303446432E303038422C73733D312C6667733D30;
CAT=NONE; CON=NONE; SIG=AAAAAAAAAAAAAAAAAAAAAAAAfQ==
X-WSS-ID: 6401DB782HO5297759-01-02
Content-Type: multipart/alternative;
boundary="=__PartCFE695F4.0__="
Content-Transfer-Encoding: 7bit