This is not “the rule,” (who makes them, anyway?)
Miss Manners. And it most certainly is the rule. However, even the World’s Most Correct Human is willing to be flexible on occasion. 
Now then. The rule used to be (back around Elizabethan times) that a woman was respectfully addressed as “Mistress,” the feminine form of “Mister”, of which the modern “Mrs.”, “Miss”, and “Ms.” are all abbreviations. “Mistress” was appropriately used with a woman’s first name and last name, whether the latter originally belonged to her father or her husband.
The title “Mrs.” for a married woman, though, later acquired the meaning of “the wife of”: Mrs. John Doe, Mrs. Robert Browning. This had some curious side effects: a married woman being referred to in a business or professional rather than social context had to use her own first name but couldn’t use “Mrs.” with it, so she (somewhat confusingly) had to use “Miss”: Agatha Christie was referred to in early book reviews as “Miss Agatha Christie,” although Christie was her husband’s name. Also, a divorced woman couldn’t call herself “Mrs. John Doe” since she wasn’t married to him anymore, nor could she use “Mrs. Jane Doe”, but had to stick her maiden name in as a first name: “Mrs. Smith Doe”, “Mrs. Barrett Browning” (not that they ever divorced, of course).
This all became a royal pain in the derriere as divorce grew more common and middle-class women entered the working world in greater numbers. So a few decades ago feminists (and people who hated having to guess what an unknown woman’s marital status might be) started pushing the sensible solution of “Ms.”, to be used with whatever first and last names a woman wanted to use (her own names, that is: “Ms. John Doe” for a married woman is as incorrect as “Mrs. Jane Doe” used to be).
“Ms.” is now the correct default title for any woman whose marital status or preferred title is unknown. However, if she indicates a preference for a different title, with whatever combination of names, that overrides the default. The old rule about “Mrs.” = “wife of” has broken down and “Mrs. Jane Doe” is now acceptable.
That’s the rule, and it’s not really very complicated. Aren’t you more comfortable now, knowing what the official correct solution is for situations where you don’t know the individual’s preference? Wouldn’t Miss Manners be proud of you? 