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.
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 22.214.171.124
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.