Well, yes I'm talking about those permisssions, however with notes it's a bit more complicated.
Notes recordset has their own permission rules, but also it matter where notes are attached.
For instance Note #1 is attached to company that you must not see, so you shouldn't be able to view this note.
But if Note #2 is attached to contact that you can see and to company that you must not see (note record is the same record), then you'll be able to see such note. So it's really important where note is attached to.
I was talking about that you've probably proved that there is a permission issue, because you shouldn't be able to see note on the search results.
Please make sure that your notes are properly linked.
We've been talking on the other topic about custom import. In fact notes require custom import to attach them properly to records.