Captive portal detection vs. automatic WiFi connection on Android (Lollipop and later)

Since Lollipop (5.1+) you might not be able to connect (or reconnect) to all authenticated (aka. password protected) WiFi networks. The culprit is called "captive portal detection". This feature is intended to help you use public (hotels, airports, etc.) WiFi access points by automatically detecting, when a router redirects all traffic to it's own so called "captive portal", where you can register your device for internet access.

Unfortunately this seems to be a little buggy and in many cases prevents reconnection (with already stored credentials) to a WiFi network. The workaround is easy, but requires a rooted device and/or some tinkering. If you're familiar with ADB, then this will be easy for you. Just start a shell, get root (eg. via "su") and use the following commandline to disable captive portal detection:
settings put global captive_portal_detection_enabled 0

You can query the current value of this setting with this:
settings get global captive_portal_detection_enabled

For some explanation on why this feature is a problem on some WiFi networks and not for others, check out this page:

As of Android 5.1 wifi networks that do not provide an internet connection are marked as bad and the device does not reconnect to them automatically.
Building into Android an assumption that an uplink to the internet is the most important network connection a device can have inconveniences users in many use cases.
An example: A wifi host that provides a Web UI for management of hardware will no longer automatically be connected to, even on an Android device that is a dedicated terminal and has no other internet connection.
Remediation: Allow the user (not developer settings) to disable this new behaviour either globally or for specific networks.

AndroidPolice explains this feature a little bit differently:

Once a device running Android 5.1 connects to a router that has no Internet access, it will remember it, and won't automatically connect to it again. This will be a boon when travelling to restaurants, hotels, and the homes of elderly relatives everywhere.
The first release of Lollipop included a few tools to help users better identify and avoid dud Wi-Fi, but now it looks like Google is simply trying to avoid useless connections altogether.

So if Android cannot connect to a specific URL, it determines that there's no internet connectivity and won't automatically reconnect to that specific WiFi network in the future.