Does it show anything in the logs when you try to send mail from hotmail or gmail on the EFA box?
If you don't receive mail from only hotmail or gmail but do from others outside your organization then that is a bit weird, I would say double check your DNS settings if everything is setup correctly.