It could be that the fact you only have 2000 odd songs makes the search not show this problem.

That is likely. I use the search often, and do not notice the problem you describe. I understand how a large list of titles might cause the problem (although I don't think they intended for there to be a problem in this case, it might need to be entered as an official bug).