What you are describing should not occur (if I understand you correctly). If the Info Item is keyworded properly (the keywords you expect do exist) then I am not sure what else you can do to cause the search to function as expected.
What type of search is being used (Quick or Advanced, if Advanced, what is the defined criteria)? If you create a new Info Database and copy an Info Item not being "found" to the new .urd file, does the same search fail to find this same Info item in the new database?
If so, can you save the search being used (in the new .urd file), then send this new .urd file to
support@kinook.com for our analysis?