[icebraining]

You just reply to any DNS request with your own server's IP, which accepts any HTTP requests with a redirection to the captive portal. The replies can have low TTLs to avoid the caching problem.

[poizan42]

The common web browsers caches DNS responses irrespective of their TTL values, which may be for as long as 30 minutes[0].

[0]: http://www.zytrax.com/books/dns/info/minimum-ttl.html

[icebraining]

Firefox and Chrome only store for 60s and 30s, respectively.

For IE, you can just refuse connections to the internal webserver for logged in users, as IE will then mark those IPs as bad and refresh the DNS: https://blogs.msdn.microsoft.com/ieinternals/2012/09/26/brai...