Yeah, so I think I'm seeing something weird where some software isn't allowing
this particular recursive query? I'll dig into it more.
By the way:
> The A record was never in the root zone.
Are you sure of that? I don't have any proof, but my impression was that the DNS registry for ai (which was also just Vince Cate...) was able to ask for it because at one time the root zone was less restrictive in what RRtypes could be placed there for TLDs. But that might just be repeating someone else's mistaken impression.
OK, I went and looked in the Internet Archive
https://web.archive.org/web/20090716164810/http://www.intern...
and this version of the root zone from 2009 does indeed not have an A record for ai, just ordinary NS delegations. So it seems like your explanation is confirmed, and there must be a change in some recursive resolver behavior. (I tried from four different Linux systems on different networks and all refused to resolve it, so there really must be something that's changed more widely, not just my home router.)