I am looking for a DNS level solution, that redirects a user to a specific IP on the first visit, than directs them to the correct IP on subsequent visits.

So the idea is, for example, if a user visits "malicioussite.com", the first time they try to resolve that DNS name, it resolves to the IP of an internal web server, showing them a warning.

On subsequent resolves, the users would get the actual IP, so they can visit the site.

How can this be achieved? I am really flexible on what I can use, as long as its on the DNS level.