Hi (and sorry for the late reply),
Sounds like you have tried a fair few fixes (a number for which would have been my initial reaction as a fix) to no avail.
You obviously still have your messages icon. Couple of questions for you.Do you still have the option to send SMS ? What device firmware are you running? Carrier? and are you on a BIS or BES ?