delete and recreate the mailbox? is it a single server AAM or do you have multiple app servers - as in, could 1 of those app servers not be getting the updated greetings? I remember Avaya being rather adamant about rebooting MM every 90 days... stop/start messaging, reboot, etc.
Beyond other things - like users from different areas covering to different info mailboxes that sound the same and you thought changing one would be fine and there's really 2 or 3 info mailboxes for that purpose...