Jag har ett svagt minne av att det finns någon app som kan göra något liknande men minns inte (tror inte) att den fungerar ihop med SMS. Mitt minne säger mig att det finns en "dialer" som accessar kontakterna på detta vis men jag hari inget minne av någon T9 implementation som du kommer att behöva för du har väl inte tänkt att köra med multitap;)
Personligen så tror jag du borde ge tangentbordet en chans. De allra flesta tycker att det fungerar bättre (och personligen så väntar jag på 3.0 med ett helsvenskt tangentbord...)