Incorrect NS record returned for domain after re-creating hosted zone

I moved my domain from a different registrar to Route53 some time ago. I created a hosted zone for it and an A record. All was working fine and DNS queries were correct and successful.
A few weeks ago I deleted the hosted zone and recreated it (for the same domain) via CloudFormation. The creation operation completed successfully but DNS resolution stopped working.

The NS records publicly available are different from the ones displayed in the Route53 configuration.

When using dnsquery.org to test the domain (NS lookup) I see this error:

Step 2
We've got referrals (a.gtld-servers.net., b.gtld-servers.net., c.gtld-servers.net., d.gtld-servers.net., e.gtld-servers.net., f.gtld-servers.net., g.gtld-servers.net., h.gtld-servers.net., i.gtld-servers.net., j.gtld-servers.net., k.gtld-servers.net., l.gtld-servers.net., m.gtld-servers.net.) from queries on previous step. We'll query them now, until we got an authoritative result
69.95 ms d.gtld-servers.net. [192.31.80.30] (United States)
;;Authority
[redacted_domain]. 172800 IN NS ns-1508.awsdns-60.org.
[redacted_domain]. 172800 IN NS ns-1795.awsdns-32.co.uk.
[redacted_domain]. 172800 IN NS ns-298.awsdns-37.com.
[redacted_domain]. 172800 IN NS ns-542.awsdns-03.net.
;;Additional
ns-298.awsdns-37.com. 172800 IN A 205.251.193.42

We got referrals from d.gtld-servers.net.

Step 3
We've got referrals (ns-542.awsdns-03.net., ns-298.awsdns-37.com., ns-1795.awsdns-32.co.uk., ns-1508.awsdns-60.org.) from queries on previous step. We'll query them now, until we got an authoritative result
32.14 ms ns-298.awsdns-37.com. [205.251.193.42] (Seattle, United States)
;;Query failed: "DNS request failed: The name server refuses to perform the specified operation for policy reasons."
1.39 ms ns-542.awsdns-03.net. [205.251.194.30] (Seattle, United States)
;;Query failed: "DNS request failed: The name server refuses to perform the specified operation for policy reasons."
1.34 ms ns-1508.awsdns-60.org. [205.251.197.228] (Seattle, United States)
;;Query failed: "DNS request failed: The name server refuses to perform the specified operation for policy reasons."
8.27 ms ns-1795.awsdns-32.co.uk. [205.251.199.3] (Seattle, United States)
;;Query failed: "DNS request failed: The name server refuses to perform the specified operation for policy reasons."

The authoritative answer from the root servers differs from the ones currently configured for the NS record of the domain in Route53:

ns-1956.awsdns-52.co.uk.
ns-1471.awsdns-55.org.
ns-522.awsdns-01.net.
ns-8.awsdns-01.com.

In fact, the Route53 tool to check the domain returns the correct entries for the NS record:

DNS response code NOERROR
Protocol UDP

Response returned by Route 53
ns-1471.awsdns-55.org.
ns-1956.awsdns-52.co.uk.
ns-522.awsdns-01.net.
ns-8.awsdns-01.com.

To rule out a TTL issue I have tried deleting and re-creating the domain twice waiting one week in between. In both cases the NS values returned by the root servers have been the old name servers.

This is the only hosted zone/domain I have in my account but is effectively unusable at the moment and re-creating the hosted zone does not seem to be helping whatsoever.

I need help. What else can I do here?
Thanks.

Edited by: OutsideCentre on Feb 28, 2019 9:14 PM