Searching for someone who has changed their name

I've got a site where I'm using RealName and someone has gotten married and changed her last name. Now when searching for her new last name, she doesn't come up in the user search. The old last name comes up still, and the RealName field has been changed in her profile.

I think I've cleared all the caches and recalculated names, and it still doesn't work. Is there an order to these that should do the trick? Or something else I can do?