Android: Connected to device. Can’t provide internet.

First try would be: use your device MAC address instead of a randomized one. You find this option under WiFi, your connected WiFi, Privacy “use device MAC”.
This did not change anything for me.

My scenario may be different as I only had this issue when travelling in China. As far as I understood Android is trying to connect / ping “connectivitycheck.gstatic.com” after it has connected to a WiFi to test if there is internet connectivity. Google is not reachable in China and there we already have the reason.

I used then an ADB shell to change a few values – everything was NULL before that.

adb shell
settings put global captive_portal_server connect.rom.miui.com
settings put global captive_portal_http_url http://connect.rom.miui.com/generate_204
settings put global captive_portal_https_url http://connect.rom.miui.com/generate_204

Not sure if everything is necessary – after that the message was gone and WiFi stayed connected.
The URL is used in Xiaomi Smartphones and is reachable in China.

I will set the values to NULL after the travel is over:

adb shell
settings delete global captive_portal_server
settings delete global captive_portal_http_url
settings delete global captive_portal_https_url