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.