Ah, yes it would have helped for you to mention iMessage up front.
As a heavy user of iMessage (and sometimes text when the network falls back to it) I've never encountered this. I had a 4S for a long time, and now message regularly with several 4 and 4S users, and I've never seen this, nor heard complaints about it from my contacts... sorry if that isn't helpful but at least I can tell you it's not happening to everyone.
Knowing the people I message with, fwiw, we keep our OS versions up to date, and nobody is jailbroken... I'm not saying you are any different, just reporting what I know.