I have purchased corby handset too.. and faced the same problem.. Here while transfering the phonebook i found nothing while searching the contacts.. later found out the solution.. actually while transfering the contacts the first name will become second name and second will become first, sometimes tact is having only first name it will become second name, and the corby handset does not use second name while searching the phonebook this is why it is displaying only some contact in your phonebook while searching. the only posible solution is to change second to first name through samsung pc suit. hope this will solve your issue.
Regards,
- Pravin Patel