I find it's a lot faster to find a contact with T9 than a soft QWERTY keyboard or just scrolling through a list. (CyanogenMod has this built in to its dialer and it is beautiful.)
From a UX perspective, after the initial learning curve, T9 gives you larger tap targets and fewer taps needed (compared to QWERTY). This naturally results in faster finger movement but also less need for movement overall. It's a win-win for search.