Another piece of info that would be helpful is the Internet Headers from a message that bounced. (The original message, not the Non-Deliverable reply).

Have Alice@External open one of the messages she sent to you that bounced and then File -> Properties. Have her copy everything in the "Internet headers:" box at the bottom of the Properties dialog and send it to you. (Using an alias I guess).

Look thru the headers and verify that it was indeed sent to the new domain, and see if you can spot the first occurrence of the old domain name (if any).