In Site Settings -> Manage security and additional settings -> Change anonymous access  settings, do you have it set to Nothing?

Yes i have set it to nothing........

We usually recommend that individual users  not be granted access  to your
SharePoint sites. Rather, use Windows Groups instead. So, perhaps you have
granted some groups access and these users are members of these groups?

See who has access to the entire site  collection (even in the portal) by
typing /_layouts/1033/userinfo.aspx in place of the default.aspx page. Like
this:
http://portal/_layouts/1033/userinfo.aspx
http://portal/sites/topsite/_layouts/1033/userinfo.aspx

We do use Windows groups and i used the link you gave but the users  from whose computer i tried does not figure in the list.

I'm at a loss to help further without physically being there.

Check if particular users  are in local Administrators group on
SharePoint server.

My team is also working on it.

I will post it here when we find a solution.