The typical route of discovering those viruses was first genetic. When you get a genome (especially back when this work was initiated), you'd BLAST all the gene sequences against all known organisms to look for homologs. That's how you'd annotate what the gene does. Much more often than not, you'd get back zero results - these genes had absolutely no sequence similarity to anything else known.
My PI would go through and clone every gene of the virus into bacteria to express the protein. If the protein was soluble, we'd crystallize it. And basically every time, once the structure was solved, if you did a 3D search (using Dali Server or PDBe Fold), there would be a number of near identical hits.
In other words, these genes had diverged entirely at the sequence level, but without changing anything at the structural (and thus functional) level.
Presumably, if AlphaFold is finding the relationship, there's some information preserved at the sequence level - but that could potentially be indirect, such as co-evolution. Either way, it's finding things no human-guided algorithm has been able to find.