Thinking about from the MMS message perspective...AT&T and Verizon use different messaging providers...additionally...and they both operate with "good enough" attitude. Anyhow, its a transalation problem. It shouldnt be, but it is. I suspect its at the root intra-messaging gateway in how it routes imessage traffic versus traditional MMS(mobile ANI to mobile ANI)...the dileneation is transpiring at the wrong place; it should happen prior to being routed to the external GW hub.
The reason you see "Message Delivered" is because the messaging GW carrier outside of AT&T is reflecting they have successully delivered 100% of the traffic, when that is incorrect. They dont submit a delivery receipt to their GW partners. So, telling the straight dope on this is unsettling, but until customers demand that their messages get delivered successfully, it will continue to be an "unknown problem". Unfortnately this is the new reality in the age of Unlimted Everything plan offerings.
As for SMS, it obviously does not have the delivery options/real time of MMS(think email in text format versus HTML format) for reality of how successful they are transmitted. There is a substantially reduced error rate, noentheless, if the messaging provider states they sent 100% of the messages successfully, there is no validation of the success rate.
As of today, March 13, 2013 that is the truth.
The tips provided above (turning off Dial Assist & re-authenicating with Apple iMessage portal) seemed to improve the issue.