But it wasn't verifiable because Voyager didn't know what Starfleet had been up to for the past X years, and they couldn't have cross-referenced the registry with current ships. Likewise, Arturis couldn't have had any current alpha quadrant information.
That's what I'm saying. NX-80000 wouldn't be something the Voyager crew could check, but they'd know the convention well enough to know that if a ship was NX-1701-F it should be Enterprise, or NX-2000-A it should be Excelsior, or NX-74656-A should be Voyager or whatever. But Arturis could use the information he had (which was apparently pretty comprehensive, to fake a message from Starfleet Command and fill his ship with authentic-looking okudagrams and computer systems) to find about the Starfleet practice of reusing hull numbers of famous ships with a letter tacked on the end, and then picked a historical name and number and added an "A" to the end for instant verisimilitude. Or an instant amateurish mistake, depending on the NX-01 Enterprise's eventual relationship with the Federation roster is.