GPOs are in effect but the curiosity is that other users don't have this issue and they also have GPOs in effect.
I was thinking maybe it has something to do with the Outlook profile. Maybe the profile is corrupted? The thing is, Outlook saves different settings in different locations. Some settings are saved in the .pst/.ost file and some others are saved in the outlook profile.
Possibly, but the ribbon customizations are per user, not really linked to the profile. Many settings stored in the registry are outside of the profile too - deleting the profile wont change the settings.
Things like the autocomplete list and categories are in the data file - but most options are in the registry.
If the affected users have a different version (like the OEM build), I'd blame the software - the version shipped on new computers uses a virtual registry and may not honor all GPOs. (Consumer versions honor some, but not all GPOs).
I would try resetting the ribbons - I had problems with my ribbon and needed to do that. (I was restoring backup copies and they'd corrupt within a couple of weeks. I gave up and reset the ribbons - its been fine since. I still have backups, but never need to restore them.)