We were recently seeing a similar (not identical) problem. It started with AT&T devices, but then spread to a small number of devices on other carriers. The symptom was that messages being sent would sit in the outbox while the device was connected to cell service. As soon as the device connected to WiFi, the messages would immediately be sent. The problem began right after we made some changes to internet routing into and out of our data centers. It appears that this was causing some data fragmentation that one of our edge gateways couldn't deal with. Until we can get that gateway replaced, I changed the MTU and MSS for the UAG appliances hosting my Secure Email Gateway cluster. THIS IS NOT A VMWARE SUPPORTED CHANGE! But, if you're using a SEG and want to give it a try, the command syntax is: ip link set eth0 mtu 1400 (sets the MSS to 1360 & MTU to 1400). This assumes the messaging traffic is going across eth0. If yours is not, adjust the command accordingly.
This change immediately fixed the problem for all of my end users. I haven't noticed any ill effects of the change, and am hoping I don't before our edge gateway is replaced. Once that happens, I'll revert the UAGs to default settings.
Good Luck!
