We had something similar, if not the same thing, happen Monday Aug 9. Some, not all, users reported that they could not see accounts in any view. And since accounts were not visible in the view, then searching did no good either. What we did find was they could go to an activity and click on the Regarding account and access the account information on the form fine, just not visible on the views. Nothing had changed on our end(I'm the only one who would have many any changes). Being that it started on a Monday, I assumed Microsoft had made a change which affected security roles. I entered a ticket with them. We don't use the out of the box security roles but have our own custom ones. I also tried clearing browser cache, but that did not make any difference on my users. Also tried Incognito/InPrivate browsing to no avail. Advanced find did not help either.
What I did was add the out of the box Salesperson role to their profiles and they were immediately able to see accounts again (kept their custom security roles). Then copied the Salesperson role and started playing with it and assigning it to one of the users. So now on to comparing the user's custom security role and the copied Salesperson role to see which of the 500+ security settings may be the culprit..... ugh. After adjusting some of the settings and not triggering the issue again, I decided to take the copied role away from their profile so they just had our custom role again and they can still see accounts (no change made to our custom role). So it sort of fixed itself. This was the following Monday (Aug 17), so my assumption is that Microsoft may have fixed the issue over the weekend. Although I have not received confirmation back from Microsoft as of today.
Long story short, try adding another role to see if the user can then see the accounts.
