Gamar, I don't know if Voda does this, but with AT&T you have access to all your call and data history on the website where you can manage your account. It doesn't have the message itself, but at least it'll have the number it came from.
Is there anyway to change the behavior of the BB when it comes to deleting messages? I like to keep a clean SMS inbox, but from time to time need to go back to a message. I've gotten in the habit to save messages I'll probably need.