You were pointed into the right direction with KB946358. LSA cache is being purged when server restarts or may be disabled entirely (but this will require restart first).
I'm very interested in finding precise reproduction steps for this. See my question about this - still no answer so far, but it contains a solution which doesn't require reboot to fix your renamed user.
You have to run following PS script on your sever where you have stale date in LSA cache once after rename:
$objuser = new-object system.security.principal.ntaccount "domain\<new account name>"
I tried this solution and confirm that it works.
Also you may find the following an interesting read on this subject:
I will appreciate is somebody will be able to explain how I can reproduce this or at least give me some idea how I can recreate the situation when "recurring queries by applications keep the existing cache entry alive for the maximum lifetime of the cache entry." (this is short and laconic explanation of issue's cause from KB946358)