I can't think of any tools off hand directly suitable for what you want to do, but you will want to do some sort of homology analysis and for what you are looking for BLAST is probably your best bet. What BLAST search criteria have you used? You didn't provide a level of how strict or relaxed your criteria were.

I find it hard to believe that a protein would be so distantly diverged that you would not find homology, so perhaps you should take "conserved" regions from your crystal structure (alpha helical and beta sheet combinations, etc. -- anything that would be unique to your protein) and specifically compare those to known databases. Do you have any idea what the functional motif of the protein is -- perhaps that has some conservation.

As far as private or public -- I think you'll find all you need in the public domain -- are there any closely related species that have genome sequence data?

PSI-BLAST against nr + HHpred? Smaller than 20% identity is not uncommon, especially with viral proteins. However, while sequences have diverged at the aa level, it's possible that detectable structural similarity still exists..