and just to ask some questions to make sure we are all on the same page:
what message app are you using?
are you rooted?
does this occur on wifi as well as cellular?
does it occur with only one sender or does it occur regardless of who sends?
do you have any sync errors when this occurs? (look in the sync tab under settings and see if any sync errors are listed--would be a red sync circle icon)