Another thing worth trying is installing Thunderbird, or similar, and see if you experience difficulty setting up the same e-mail accounts under Thunderbird.
I don't believe this problem is rooted in Outlook 2016. You need to take diagnostic steps to determine where the "hitch in the gitty up" is actually occurring. It could be in Outlook 2016, but without a comparison between it and another email client its virtually impossible to know.
The above presumes that the access method is IMAP.