SharePoint Online Issue Opening Documents - Windows 8

Recently (since about 7/6/2017), I see two of my users on Windows 8 starting to experience dead-slow response in trying to open documents from SharePoint Online in Excel/Word. The users get message indicating 'waiting information from server...'

Same settings were working fine for past more than 8-9 months without any issues. The response time is easily more than 20 minutes, so obviously this is impractical.  To get around, the users are downloading the documents to open and make changes and upload back on sharepoint.

We tried regular tricks like reseting the IE 11, having the site in trusted site, not detecting automatically the proxies. But nothing worked so far.

Appreciate any help to troubleshoot this issue. Thanks.