Deleted Exchange Mailbox User is still there - somewhere!
Our organisation has an email setup whereby two sites all have the same email suffix, the @domain bit. This did initially cause us routing issues with our SBS / Exchange 2003 setup as we had a situation where a@domain was at the local site and user b@domain was at the remote site. So local emails were obviously delivered to the local exchange server and the other site's mails had to go to an ISP. Anyway, that's just a preamble.
The problem I have now is that a user who was local is now remote so I've had to change the routing. I deleted the user and the associated mailbox and ran the mailbox cleanup utility. As the user no longer exists locally then mail to his address should follow policy and route for external delivery but it doesn't, it still tries to route locally and then obviously returns a "mailbox not found" error.
What have I missed to remove all traces of this user?