gmail
In Google Apps I re-issued the e-mail address of a former colleague to a new colleague with the same first name (our format is firstname@domain), but now every time I want to compose a message to the new colleague the wrong (old) name is associated with the e-mail address.
Note: the name has been changed in the settings of the new account of course 🙂 It's just that my "local" Gmail client keeps autocompleting the wrong name when I type the e-mail address.
On one of my accounts, the name was updated immediately after sending an email message. On another account, I just checked back after several minutes, and it showed the right name. So it seems that this is either a delayed process, or you must invoke some functionality (e.g. send an email) for Gmail to pull these settings from your account.
I had a similar problem - for me the answer was to not only have the new address added as a "Send mail as:" but also to choose "Send through X's SMTP servers"
Best Answer
Ok, apparently all it took was updating the name in my Google Contacts, which apparently uses the e-mail address as the primary key :-/ Never used Google Contacts before, so I completely missed that.