This depends a lot on the culture, so, as they say, your mileage may vary. For me, using honorifics is mostly out of the question except for señor or señora. Using señorita for unmarried women is still heard of, and there's no suitable neutral replacement equivalent to English Ms. Female kindergarten and primary school teachers are customarily termed señorita but it's mostly by their pupils and their parents. I've never heard don or doña being used in formal calls.
I employ academic titles only in the most formal situations, mostly doctor, arquitecto, ingeniero, profesor and their feminine versions, only when I'm sure that the other person is normally addressed like that and/or insists on it. If not, señor and señora.
If I know the full name, I use it. This I find best if the other person has a very common surname like Pérez, García, López, etc.
I usually begin by saying «Mi nombre es... y estoy llamando desde... Quería/Querría/Quisiera hablar con... ¿Se encuentra él/ella?» or something like that. If I begin formally like that and the other person replies informally (i.e. by calling me by my first name), I tend to switch to the informal register immediately (but that's me and my usual kind of exchange).
If the person I want to talk to picks up the phone and I recognize their voice, I might simply say «¿Hablo con...?» to confirm. If not, I assume some receptionist or secretary is talking to me and proceed as above.
This all applies to calls from my office. I seldom call anyone formally for private purposes. When doing so, I guess I would be leaving out my own identification and just get to the point of asking for whoever it is I want to talk to, or simply state what it is that I want in a conventional polite register («Quisiera averiguar sobre...» or «Llamo para preguntar si sería posible...» or the like).