No idea where the data is stored. Are you connected to any IM/Skype provider? It may be that what you are seeing are the contacts coming from those accounts?

At least in my case, I had the vage feeling that the problem first happened when I logged out of Skype while having the recent contacts opened, but I'm not sure, and I don't use Skype anymore.