The most likely explanation is that the two users have different access, so one person is seeing results the other person does not have permission to view.

I would start by comparing the list of results to determine which ones are not visible to the other user; at that point you can start looking at folders, security tags, etc., to evaluate access rights.