I'm not quite sure what your requirements are. Do you want to host one Domain for yourself? Or possibly thouthands of domains for others?
Also "handles millions of queries" - millions of queries in what? A month, a day, an hour, a minute?
I now assume that you want to host a handful of domains for yourself which get requested 1000 times per minute. So about 17 req/sec which is fairly low on traffic.
I can only speak for Germany. Here you can get relatively cheap virtual Servers as well as DNS service.
http://www.hetzner.de/en/hosting/domain/registrationrobot/
They charge the service of three Nameservers at 0.59 Eurocents per domain per year.
If you want to run your own DNS the cheapest available virtual Server will suffice. If you run PowerDNS which I can highly recommend, something like 128MB core memory and some slice of a single CPU Core will be more than enough.
Take a look at http://www.server4you.net/vserver/
The cheapest vServer is charged at 8.85 Euro per month. It includes 3GHz CPU Power, 1GB core memory, 25GB HDD and 5TB traffic. Which I think is more than sufficient for your DNS requirements.