I too have been plagued with the horrible SMS keyboard lag, and had stopped sending any messages for a while. I got bored today, and since the consensus seems to be that it is the backups being restored that kills it, I wiped out the SMS database from my phone, let it rebuild, and restored it myself. I'd like to report that all lag is now gone from my keyboard 
Here's what I did (this assumes the phone is jailbroken):
1. Make sure the SMS app on the phone is not running. Get into the bugger with your favourite FTP app, and navigate to /var/mobile/Library/SMS.
2. Drag the file sms.db out of there onto your desktop or something to make a backup of it. Delete the original on the phone.
3. Launch the SMS app on the phone, and it should be like the first time it was launched; no previous messages, and it throws up the keyboard and such to type a new one. Close the SMS app.
4. Refresh the view in your FTP app, and you should see a new sms.db in there. Drag the one from your desktop into there, and overwrite the new one that was just created.
5. Launch the SMS app on the phone again, and you *should* have all your messages, and the keyboard should be non-laggy!
Hopefully this helps a few of you out there; it seems to have worked for me. The non laggy keyboard lasted through a reboot, and it seems to be fine. Good luck!
Here's what I did (this assumes the phone is jailbroken):
1. Make sure the SMS app on the phone is not running. Get into the bugger with your favourite FTP app, and navigate to /var/mobile/Library/SMS.
2. Drag the file sms.db out of there onto your desktop or something to make a backup of it. Delete the original on the phone.
3. Launch the SMS app on the phone, and it should be like the first time it was launched; no previous messages, and it throws up the keyboard and such to type a new one. Close the SMS app.
4. Refresh the view in your FTP app, and you should see a new sms.db in there. Drag the one from your desktop into there, and overwrite the new one that was just created.
5. Launch the SMS app on the phone again, and you *should* have all your messages, and the keyboard should be non-laggy!
Hopefully this helps a few of you out there; it seems to have worked for me. The non laggy keyboard lasted through a reboot, and it seems to be fine. Good luck!