If you know their true friend code?? I have had it happened to me but i usually just click on their text box and add them again. But i really dont know how to give any further advice maybe if the friend pvped a lot ask around the arena if anyone knows them, or wherever your friend may hang out a lot on the game just ask around if someone knows them. I know some people that have found success with doing that.
