I have a domain registered with ISNIC (domain.is). They only let you set nameservers that pass their requirements. I've been told it's this requirement that I need to fix:

Nameserver must be consistently registered in DNS, i.e. its own A resource record must be available and a corresponding PTR resource record as well.

I allocated two new IP addresses from my server host and at that point set their PTR records to ns0.domain.is and ns1.domain.is. After that I created two A records for that domain in Plesk, again ns0. and ns2.domain.is with their respective IPs.

Next, I went to the ISNIC page to register my nameservers, along with their IP addresses I'd allocated and this worked perfectly for both without error. So the final job was to set the nameservers for the domain via ISNIC's control panel, however when I try, I'm getting this error:

Test results for "NS0.DOMAIN.IS":
The nameserver ns1.vps123.vpsprovider.com is not consistently registered in DNS (ns1.vps123.vpsprovider.com => 1123.123.123.123 => vps123.vpsprovider.com)
The nameserver ns0.vps123.vpsprovider.com is not consistently registered in DNS (ns0.vps123.vpsprovider.com => 1123.123.123.123 => vps123.vpsprovider.com)
The nameserver ns0.DOMAIN.IS is missing from the NS record set for DOMAIN.IS
Test results for "NS1.DOMAIN.IS":
The nameserver ns1.DOMAIN.IS is missing from the NS record set for DOMAIN.IS
The nameserver ns0.DOMAIN.IS is missing from the NS record set for DOMAIN.IS

This is really at the limits of my DNS knowledge I'm afraid. It feels like I'm close but maybe missing a vital part, linking the nameservers in Plesk or something?