Is there an iPhone 3GS app that stores incoming SMSes encrypted?
I don't think that's possible. You could send Encrypted SMS, though. So, in the end, you'll have them encrypted. Black SMS could do the trick. Extracted from Gizmodo's review:


  Here's how it works. When you download the Black SMS app, you attach a password to your message and then type whatever you'd like into the app. Once the message is complete, hit Send and the app will automatically open your SMS app. Paste the message and the recipient (and everyone else) will only see a black text bubble. SECRET AND ENCRYPTED BLACK TEXT BUBBLE, that is. The person on the receiving end then copies the black bubble and unlocks the message by pasting it into Black SMS with the password. If it sounds convoluted, well, it is. But hey, keeping secrets ain't easy.