Just to add my name to the list of users for whom Hotmail sync has recently stopped working, with the exact same error message: Invalid host address for Mail for Exchange server

All the normal tricks (e.g. recreating the account) fail to fix the problem.