Usually when I try to find people by city, country, fullname, etc. (but no by username) I got not same find results!

I think it's not really Linux bug, but I don't have Window$ to try.

Search the forum for "user search" things. In short, since Skype search does not use a central directory, we cannot guarantee the same results across searches, since people come online/go offline etc.