I’ve seen some strange issue lately (similar to this one), with one of our CRM Online deployment. We had 2 users, in the same BU, with the same security roles.
Problem was:

1. First user was able to access CRM records based on priviliges
2. Second one was “blind” – couldn’t see any records

After looking at all possible settings, the solution was:

1. Add System Administrator role to second user
2. Remove System Administrator role from second user

After that, second user could “see” again. Don’t know if removing all roles or any other than System Administrator would do the trick.