I was just thinking how great I was at Graffiti on my old Handspring PDA and it occurred to me to search the market (yes, I'm not that quick).

Reviews are mixed (aren't they always?).
I'm going to try it out.
https://market.android.com/details?id=com.access_company.graffiti&feature=search_result