The only explanation that makes sense to me is that HIV has emerged previously, but only in dead-end strains that have very low infectivity, rather like the HIV-1 groups N and P mentioned in the article. Whilst it makes sense to me, I have a feeling that it can't be right; seems a bit too easy or convenient to explain.
Are we victims of a million-to-one chance mutation, but a chance that become steadily more likely as time progressed?
Further, is it just a fact of life that we can - and should - expect another HIV-level-of-infection virus to emerge in the future?