It has to be an email address thats assoicated with their Passport Account.
http://www.passport.net/
Not just, one of their address's that they use. If its an address that is Assoicated with a Passport they have, then... I don't know, something could be up on the servers end, or you might need to Repair Messenger...