Google Apps? Windows Live? Could you be more specific? All users are in the same organization (same domain) or do they want seperate domains/servers? Can it be outsourced or do you want to host all servers/services yourself?