I have had the same problem and I've turned on the less secure apps function. That didn't work.
I found a check box in the Tools > Accounts menu for the gmail account that wasn't working. I had to UNCHECK the box that says "Always use secure password".
Magic it works now. This was after trying the capcha and following all the other advice in this thread. Nothing worked with that box checked.
I'm running OUTLOOK 2011 on a Mac. If it works now for that old app it should work for the newer 2016 etc.