"Miss Li is our manager."
Well, it can mean prostitute in the wrong context, so you certainly want to be careful how you use it. From what I gather, it's pretty safe if you use it with someone's name (i.e. Miss Li), and it's pretty common in formal situations, but its connotation seems to vary by region. I see the full range of perspectives, from "it's no problem, go ahead and use it" to "absolutely never use it".
Although it's probably pretty unlikely you would really offend someone, I would probably favor using something like 女士, 姑娘, or 美女 instead just to be safe. Unless I heard someone use 小姐 before me.
That is certainly true, and I agree 100% with your original post's summation. I just know personally that a lot of people (including myself) are very uncomfortable with being addressed by those two, however, so it's something to be aware of. 美女 is probably the safest of the three terms, as it neither implies one is of advanced age like 女士, nor can only be said to someone a generation or two down from you like 姑娘. Of course, a lot depends on intonation, as does most everything in Chinese.
I once talked to a Chinese girl (online) who said that instead of using 小姐, I should call her 错过. I had never heard this before, and when I said it sounded as though she had committed an error, she just laughed. Is 错过 really an accepted form of address, or is someone having a laugh at my expense? (I know that 错过 can be a verb, meaning "to miss," as in getting an answer incorrect, so I did wonder if someone was playing a joke on me...)
If it is legitimate, though, does it have any sort of connotations does with regard to age, etc? Or, is it a relatively new term? (I started studying Chinese in 1985, and it's really amazing how much some things have changed since then! )