lammert - 4:18 am on Jun 23, 2010 (gmt 0)

What TTL times did you use for the MX records of the domain before the switch? If the MX records had a TTL time of one or a few days, it will take at least that long before the old entries start to timeout in the caches of caching DNS servers around the world. And there is a small fraction of DNS servers--especially those serving networks behind a slow Internet connection--which don't use the TTL times you defined but have their own timeout policy.