@H.Flashman(VC): You are correct, due to the latency and the fact that the genitals are not obviously involved (unlike syphilis and gonorrhea among others), actually realizing that it is an STD is problematic (why I put in "if and when"). Medical statistics were something that came about slowly beginning in the early 19th century. OTL it was the presence of AIDS in a distinct group (gay men) that started the investigation and it went from there. In the 18th & 19th centuries while there were gay men, and subsets that were promiscuous, identifying them would not be easy as the "closet" was where they lived.
@Arcavius : The fact that bloodletting instruments were not sterilized is unlikely to lead to any significant HIV spread. They were usually cleaned of obvious blood, and unlike shared needles among drug users, were not used from one person to another with fresh blood on them as a routine. The HIV virus will only persist so long, especially in dried blood on an instrument. While HIV has been transmitted to a person through a cut in the skin this was with fresh blood, the usual means of infection is through IV injection or deeper viral injection with contaminated needles or instruments. Having said that, yes there will likely be some transmission via contaminated medical instruments but it won't be a major issue.
One real serious problem is that OTL things like handwashing, antisepsis, and so forth, were demonstrably effective in dealing with disease spread. Given the immune depression of HIV, these measures may not be seen as effective as the widespread presence of HIV will mean that using these methods (and similar) won't matter very much. OTL the effectiveness of these very basic methods was demonstrated conclusively in relatively small studies, but to prove it here you'd need to segregate HIV immune depressed patients from ones with healthy immune systems which won't be possible.
This scenario WILL result in a worldwide spread of HIV with only isolated populations being disease free. The spread will be slower with sailing ships but it will happen. Over decades you'll see a massive population collapse, and lower birth rates and child survival (HIV transmission to the fetus) and collapse of "modern" civilizations is possible. Trial and error may mean eventually chastity and single partners are the only way to have a chance at being safe. There are folks who are naturally immune/able to defeat HIV (very few cases) and natural selection will come in to play perhaps.