This was one of those "pull your hair out" cases, with a completely non-obvious cause and, thankfully, a surprise happy ending.
While troubleshooting a VPN connection problem for a client, we noted the inability to connect to some PPTP VPN servers while behind any TELUS (Canadian ISP) provided Actiontec V1000H DSL modem/router.
Of course, we didn't initially connect the dots, and tried all order of troubleshooting steps related to client OS (Windows 8, 8.1, 7 and 2008 all were unsuccessful, as was iOS). Strangely some Hyper-V hosted test VMs were able to connect, which indicates that they somehow must encapsulate the packets differently.
After much head-scratching and hyper-specific web searches, a few articles were found discussing Actiontec devices arbitrarily blocking GRE - the mysterious and troublesome protocol that allows PPTP to work.
Sure enough, if we then tried all of the same devices connecting to PPTP over a cellular connection - bingo - they worked like a charm! This ruled out the OS at least.
Sadly, these combo router/wifi/modems provided by telcos are wonderful non-user-serviceable and tend to be patched and upgraded at the whim of the provider. We needed a resolution though, as these are widely deployed with our customers and their employees so this could be a big support nightmare.
In a rare win, however, TELUS came through and provided a heavily upgraded firmware for the device which not only resolved this issue, but improved the overall DSL connection speed and dramatically improved wireless range, stability and performance. As a bonus they've added IPv6 support internally, and for a future external deployment.
Solve your headaches: call TELUS (or your local equivalent) if you have an Actiontec V1000H or V2000H and ask for early access to the latest firmware. It makes a dramatic difference. You're VPNs and WIFI devices will thank you!
The magic firmware versions:
V1000H: 31.121L.11
V2000H: 31.122L.11
On the flip-side - the broken buggy firmware version appears to be 31.30l.57.
For another common and annoying issue with Windows L2TP VPNs see our older article here.
Yes, we know PPTP is ancient and proven somewhat insecure, but it's still generally the easiest to get going for basic needs without all the bother of IPSEC or certificates.