Brilliant idea there ginggs!
This adds a new angle to the testing.
By the way in case I have not mentioned, all this testing is using prepaid sims only, on both networks.
So I forced the Cell C HTC DHD phone to roam on Vodacom.
My network data connection gets "dumbed" down to EDGE speed only, even though I have a rock solid 3G signal on the other V858 phone. Tried several reconnects, but remains on EDGE only. This is probably part of the data roaming agreement?
Surprised to see that I get an IP address in the normal Cell C 197.x.x.x range and not one in the 41.x.x.x range like the V858 has at the moment. So even though roaming (made sure of that Operator=Vodacom SA), I still have a Cell C IP address and all the original problems are still there..

...as ocleroux has said...still getting handed to Cell C network.
Some connections on the HTC Cell C still sitting "hung" in CLOSE_WAIT state and no "push".
Then let the phones idle for a while till they only each had an established port 5228 connection.
(HTC still has those "hung" CLOSE_WAIT connections)
Test Results:
Cell C HTC (roaming) to Vodacom V858
whatsapp message - within seconds
Gtalk - within seconds
Gmail - within seconds
Pointless to test the other way yet as the Cell C phone has active Gmail and whatsapp server connections and will work.
Then let phones idle again for a while, till only established port 5228 connections exist on both.
(Although the HTC still shows several "hung" CLOSE_WAIT connections, including the Gmail one)
Vodacom V858 to Cell C HTC (send time)
whatsapp (13:16) - No notification, but when I opened whatsapp there was the message tagged with 13:17? Maybe the whatsapp server tag time and not actually the time it was received by the whatsapp client app?
Gtalk (13:17) - Message received at 13:36
Gmail (13:18) - Message received at 13:36
It is now 13:27 and still no notifications from any of the above on the Cell C HTC, even though it has an established port 5228 connection.....
13:36 updated the above...
My money's still on the broken inbound on port 5228 on Cell C.
Off for a lunch break...
Then going to dig out a Vodacom prepaid sim and put in the HTC, just to make sure this is not a phone specific thing!