Well there's only one PDA with more power than a T3 which is the new Dell Axim X30. All other top-end PPC's use 400Mhz processors, as does the T3, and voice recognition is possible on PPC's. I'm not sure what the PPC recognition amounts to though, it may just be navigation and not actual typing...
I used to use a P2 (333Mhz) and it had some voice recogintion software. I know that doesn't necessarily mean there'd be enough on another platform, but I'd guess other factors (like microphone quality) would be more limiting than processor speed.