I have been having this problem since I purchased my phone last July!!
Just to throw this out there: First, the Fascinate forums would be more appropriate for you, as not every phone, build, app, etc, are equal. So a solution for one might not be the same for others. As for the causes, it can be many. With the Galazy Nexus for example, most of the issues were just because the major players (Handcent, GO SMS), hadn't yet been bug-fixed for ICS. The stock app rarely had this happen, if memory serves.
Also, the whole FCC thing...wellllll....as far as privacy goes, I think you're gonna have a little bit of a hard time getting through all that stuff, just because of that. It's almost like saying that if you pass someone a note in study hall and someone else happens to grab it off the desk first, that somehow it's illegal or something. Just as in e-mail, and everything else electronic, if it's THAT sensitive, it shouldn't be done via text. Also can't blame the carrier all the time for everything. Sometimes, cross-carrier messages get borked. It even says that in fine-print somewhere for some of them, I think. Also, you mentioned that the VZW guy put Handcent on and it was working, then the issue came back. You failed to mention if you had ever updated that app, if you uninstalled and tried stock again, whether your buddy/dad/etc are on the same carrier, etc.
Again, I'd suggest the Fascinate Forum, with a little more detail to your specific case (without the whole anti-Verizon overtones that it seems to have), and see if they can uncover it more. Again, is your phone stock, is it rooted, what apps do you have, etc.