There was a thread on a simular situation to this awhile back. Turned out that the push message was stored on the SIM chip. I don't know if this is the same but they corrected it by putting their SIM in a phone that allowed deleting this type of item from the SIM and deleted it. Worked after that according to the thread. You might try searching for that thread.

Hope this helps.
Rcbjr