PPTP VPN requires the use of the GRE protocol. When you run on a NAT'ed IP (as in Vodacom's case) the GRE protocol does not route properly. Without the GRE protocol, PPTP VPN will not work.
OpenVPN should work as it does not require the GRE protocol, but I might be wrong.
End user demand has forced the standards bodies to rethink this and you can now reach most IPv4 sites/servers from an IPv6(-only) connection. You need some blackboxes in the network to make this work and these devices are just NATing the traffic. This is unlikely to solve the current NAT issue.
Why don't you just IPv6 enable your server so that it can accept either IPv6 or IPv4 connections?
I've been doing IPv6 over wifi on my Android phone for a couple of years now with no issues. My next phone will have to support IPv6 on the UMTS side as well. Probably the Galaxy Nexus which has the correct Radio Interface Layer (RIL) capabilities for IPv6 PDP contexts.
footnote: Do any of you realise that MyBroadband has been IPv6 enabled for about a year already?
I have clients who are still having problems. The have been provisioned on the InternetVPN APN and have made the necessary changes. This has improved things as they no longer get 10.x.x.x addresses, but the are still unable to connect to VPN's when they get addresses in the 41.13.x.x range. This is in Joburg, northern suburbs.
Anything else we can do?