I have a habit of saying 'До свидания' (Au revoir; until we meet again) when terminating a conversation. Would this seem strange if I'm not likely to actually meet that person again, such as a clerk, a stranger asking for directions or just somebody who called the wrong number? Should I instead be using 'Всего доброго' (All the best) or a different farewell entirely?
It's perfectly normal;
до свидания is just a polite form of a farewell and is used regardless of the probability to meet again.
до свидания can be used in (formal) phone calls, when people have actually never met and probably never will.
Всего доброго is also fine and, I think, perfectly interchangeable with
A way of saying goodbye that implies that it is likely that you won't see each other again is
or the more polite (or plural)
Yeah, and I agree with Lev that до свидания is perfectly normal regardless of the probablity of meeting again. It's just that if you want to imply that you probably won't meet for a long time or ever, прощай(те) is a better choice.
The most informal way to say goodbye is "Пока", cognate to Italian "ciao". "До свидания" is totally OK, and this is just like you use the "How are you" greeting in English – just a formal way to mark a specific situation.
More close to "see you" is "увидимся". This actually means that persons involved in conversation are saying goodbye to each other (попрощались друг с другом) and that they most probably will meet in the near future.
Practice shows that it is perfectly acceptable to say
До свидания regardless of whether you think you'll actually see them again.
Think about it ... you can't possibly know if you'll see them again, you may.
Even if the person is terminally ill, I believe it's still OK to say
До свидания, implying that you'll meet them again in the afterlife at some point in the future.
In Russia "до свиданья" can be used in either case of terminating the communication.
If it is a voice or tete-a-tete conversation, then "до свиданья" will have different meanings depending on the intonation. These meanings include (but are not limited to) friendly "see you later", "hope to see you soon" etc., or a disappointed "hope to never see you again".
You should use "прощай" only if you want to stress that you will never (really never!) meet again. It could be deemed to be rudeness or threat. I recommend never use "прощай" if you unsure.
It could be used at the end of the romantic relationship. Or if you or another person should die shortly. Or your familiar is going to move to the far place and you don't expect to see it again.
"До свидания", "всего хорошего", "всего доброго" is usually used at the end of the conversation (regardless will you meet again or not). You could use "удачи" as less formal form (but still appropriate in many cases). "Пока" is used in informal conversations (mostly with friends).
There are a lot of another forms: "до встречи" (if you are going to meet again), "ещё увидимся" (less formal form of the same), maybe "созвонимся" (if you are going to chat via phone), even "спишемся" (if you are going to communicate via email/IM), "давай" (like "пока").
Often couple of phrases is combined, e.g. "Ну пока, удачи", or "Давай, ещё увидимся".