Vps – DNS config issue: Too few IPv4 name servers (1)

Your configuration file sets

allow-query     { localhost; };

That means BIND will only respond to queries from it's own server.

[jonv@desk ~]$ dig @66.215.210.17 example.com. soa

; <<>> DiG 9.7.6-P1 <<>> @66.215.210.17 example.com. soa
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: REFUSED, id: 59075
;; flags: qr rd; QUERY: 1, ANSWER: 0, AUTHORITY: 0, ADDITIONAL: 0
;; WARNING: recursion requested but not available

The 'status: REFUSED' is the big indicator of what's wrong.

Edit: You should be able to just remove the line, the default is allow-query {any;};. Without understanding your environment further, it's hard to give you an exact answer. You can also put the allow-query line within the zone statement for example.com while leaving the allow-query { localhost;}; in place for the global setting.

Firstly, may I congratulate you on what I think is a well-written, clear, and well-researched question, and for not redacting the domain name; that last is hugely helpful in answering.

Let me address the substantive issue, if I may: the whois points to a different set of nameservers than those which you have set up to be authoritative:

[me@risby ~]$ whois earechnung.at
[Querying whois.nic.at]
[...]
domain:         earechnung.at
registrant:     MAT8777331-NICAT
admin-c:        AT8777330-NICAT
tech-c:         MH536567-NICAT
nserver:        ns1.your-server.de
nserver:        ns3.second-ns.de
nserver:        ns.second-ns.com
changed:        20121004 15:29:23
source:         AT-DOM

Note the three listed servers. I freely concede that you have those servers set up to serve NS records that point the query elsewhere - but you also have them set up with data to respond to the authoritative request, and their server believes itself to be authoritative for the zone and can therefore lawfully return authoritative negative responses for RRs it doesn't know about. The right thing to do in this case is go back to the registrar, which I think is Hetzner in this case, and change the nameserver records not in their DNS server, but in their registration server - the device that populates the whois for .at. - to return your two new servers ns5.kasserver.com. and ns6.kasserver.com.

The business of serving a set of NS records to delegate a subzone works perfectly when it's used to do that: delegate a subzone of the one which was followed to the current set of nameservers. Using them more like an HTTP 301 redirect is unusual, and - as you have found - may not work perfectly.

As to best practice, it's completely normal to use one provider for registration and another for DNS provision. That said, the two tasks are often so closely welded that some registrars can't cope with having a registered zone on any DNS servers but their own. If Hetzner is one such, you will need to move the domain registration to a different registrar.