I honestly have never had this issue. It's really about focus and effort. If the person is important enough, I will most likely remember how to contact them. I also mostly use email for all important communications so that remains searchable. The other chat apps are all for casual friends and acquaintances that if lost, well so be it.