I think OP means that the search function was there in the earlier iPods, but got "removed" from ipod Touch/iPhone.
And while the alphabet list on the side is useful for finding single songs, there are times when I want to search for, say, all songs with the word "love" in the title. Or, you know, I can't remember the first word of the song title, only word(s) in the middle. In fact, I'm somewhat disappointed the Touch/iPhone doesn't have a function to let you create on-the-fly Smart Playlists. Considering the versatility of the iPhone interface, it seems very doable, don't you think?