SMS messages won't delete no matter what
You could always download Handcent and use its "Force Deletion" feature. I've seen that work for many others. But depending on how many SMS you have, you will need to let it sit for a while.