I have not seen dynamic user name lookups work well in practice though, where the system has made it convenient enough to actually be used consistently. A different approach might be to leave the name as is for past conversations but use the new name for new interactions (and some way of showing the past name, xxx (formerly yyy) for new posts and xxx (now known as yyy) for past posts) - as is quite common that people manually do in the real world (and on facebook). Not perfect and quickly gets complicated.

I'd argue that a username does not have the same function as a name. My name is not an identifier and most have not chosen their name - which is also why (I believe) the first name change is free of charge where I live. In most cases you can also create a different account. Depending on the type of service this might not be desirable but in others it is exactly what you would want.