SharePoint menu labels not displaying same values for all users (SPO)

On an intranet environment of one of our clients a weird/annoying problem occurs which I have attempted to solve (without positive result).

Inconstancy in the menu:

In the menu, normal users see older versions of the menu labels.

See this example, the screenshot shows how the menu should be, created by (me) the site admin:

This is what a 'normal' user sees, this user has permissions to see all underlying pages the menu is pointing to:

This is how a user with at least 'read' access sees it. You can see the site-title is different, some labels are different and also some of the icons are not showing. Why is this the case?

What did i try to solve/investigate this (to prevent people suggesting the standard mitigation actions 😉 )

• Tried it in different browsers
• Tried it in incognito mode in different browsers
• Changing the labels, publish, check, change it back, publish etc.
• I cleared all internet caching and stuff, no results
• There is no audience targeting active, on any site

(I have blurred some content because to prevent it from displaying our customers information)

Does anyone else had similar issues? What are things i could try/do.

Thank you all in advance.