Global access rights are being provided via Groups
When a single group is removed from a profile, the accesses granted by that group do not get removed. The individual access rights are not visible under the 'Global Access Rights'. But, the accesses are still present. For example: If the removed group provided access to Projects, then the Project rights are not visible in 'Global Access Rights'. However, the profile does not loose access to Projects. They are still accessible via Home -> Projects
This even after a fresh login
It happens to only some profiles
Resolution
Remove all groups from the profile, and re-add them.