You must check that parents of those menu are not also linked to different groups.
To see a menu entry, the user must have the right to see all the menu entries in the paths.
I found out that the parent menu access was given to various groups in some other module. I removed those access rights and everything is working fine. Thank you!