I'm using Nokia 5800. Where does the phone stores all SMS messages that I'm sending and receiving? I would like to delete them permanently.
sms messages
In a private subdirectory (folder) under \private in phone memory, which is not accessible by any regular software (requires special privileges, the so called AllFiles capability to read and TCB to write). You can reformat the phone memory, if you don't trust deleting the message from the Messaging app is enough.
If you want to go a step further, you can reflash the phone with new firmware.