Searching for clearing DNS cache on android then the most common answers I found are
- Toggle airplane mode
- Reboot the device
- Open Chrome enter chrome://net-internals/#dns and select DNS and click Clear host cache
Of all of those the one you have already tried, toggle airplane mode, seems the easiest and quickest.
The only other thing could be to check the website forum for the OpenVPN client you are using on your Android phone and see if they have any suggestions but looking at my OpenVPN for Android app there is nothing related to the android’s dns cache, only the dns servers that it will use once the tunnel has been created.
It will depend very much on what TTL has been set in the dns resolver being use in your android phone. Numbers I have seen mentioned are that the ttl can be 2 hours but a few mention longer.
So I think toggling the airport mode seems the simplest solution.
How often does your ISP change your IP address?
If it is not that frequently, say every week or so, then you could just try connecting first with your OpenVPN client and only if it does not connect then toggling airplane mode and trying to reconnect again.