Your test case is absolutely correct and should work without any problems.
You can data bind the search input as well as the verification step. I recorded a shrot video as a demonstration.
In order to help you best please send us the execution log.
A Jing video demonstrating the issue may also help us to better understand what is happening. You can send us the test project also for further investigations.
An options is to add a WaitForExists to the element you are verifying. It may appear slowly causing the verification step to fail.
Thank you for your cooperation.
All the best,
the Telerik team