The current packages on Debian have a hardcoded limit of 10K names. The software is meant for routers with low memory but servers nowdays have GBs of memory.
I created a personal fork for dnsmasq that removes the cache limit of 10000 names. Meant for modern servers with lots of RAM.
A cache size of 1M names uses about 100MB or RAM.
You can install my binary packages for Debian Jessie from
https://drive.google.com/folderview?id=0B38VG7HG0bZ2Z2d6YVl0MUNvVEk&usp=sharing
After installing, hold the package with
sudo apt-mark hold dnsmasq dnsmasq-base
To setup dnsmasq follow the Debian wiki
https://wiki.debian.org/HowTo/dnsmasq
Later increase the cache-size value to 1000000 in the file /etc/dnsmasq.conf
# Set the cachesize here.
cache-size=1000000