I have successfully connected to a PPTP VPN on Android. It is configured simply with an IP address, and no MPPE encrpytion. However, it does not show up under the Always-On option.
I am running Android 4.3 on a Nexus 4.
Android Enthusiasts Stack Exchange is a question and answer site for enthusiasts and power users of the Android operating system. It only takes a minute to sign up.Sign up to join this community
I was having this issue too. Apparently Google doesn't deem PPTP secure enough, so they disable it from the "Always On" menu.
Setup DNS options for VPN connection. You may use any public-available DNS servers, for example 184.108.40.206
Note: Android 4.4+ have bug in the Always-On VPN feature: VPN stay connected, but all traffic is blocked because bug in system firewall. For fix this issue search AlwaysOnVpnFix application on Google Play.