I just discovered SMS Backup+, which connects with your Gmail account to backup all of your SMS messages. If you perform a wipe on your phone, you can also use it to restore all of your old messages (except it cannot restore MMS's).
Neat, free program.