Google reports about 2.130.000 results for "deliberate choice", so I am going to go ahead and use it, but in the mean time, I thought I should ask for an opinion from a strictly linguistic point of view: isn't "deliberate choice" a pleonasm? Doesn't the meaning of "choice" necessarily contain the meaning of "deliberate"?
Merriam-Webster defines deliberate in this sense as "characterized by or resulting from careful and thorough consideration."
Since not all decisions are made with careful and thorough consideration, not all choices are deliberate. So "deliberate choice" is not pleonastic.
Deliberate is not pleonastic at all.
OED Deliberate adj.
1 b. Of an action, undertaking, etc.: carefully considered; done with full awareness or consciousness. In later use also (chiefly in negative sense, of an action regarded as undesirable or reprehensible): intentional; done on purpose rather than by accident.
Which is quite different from
A: Shall we go for a beer? B: "Yeah... OK..."
In which B is really not concerned whether he goes for a beer or not and has given no consideration to his answer.
And is exemplified in
A: "I chose you for the job not because you are qualified, or even because you are dexterous. I chose you because you are the most expendable of the group."
Choices can be made without much, or even any, thought.
I agree with your original intuition that "choice" implies deliberation. However, this fails to account for the fact that "deliberate" serves as an intensifier.
Note MW's definition of pleonasm:
:the use of more words than those necessary to denote mere sense (as in the man he said) : redundancy
In other words, a pleonasm would imply that a phrase without the offending word would have the same meaning as the phrase with it.
In this case, it would mean that "choice" conveys the same meaning as "deliberate choice," which doesn't occur.
For example, if I were to say:
Jack made a deliberate choice to use Folger's coffee grounds in the office coffee maker
then I'm implying that Jack's choice was an incorrect and offensive one (which it obviously is — who uses Folgers?). Thus, the use of "deliberate choice" can only contribute to, or detract from, a sentence's intended meaning, and can thus never be redundant.
Or this example:
Jack made a deliberate choice to pick up his child from daycare in lieu of his wife.
The inclusion of "deliberate" here, implies that this choice is especially noteworthy in some way, which may or may not be the intended meaning.
A Hobson’s choice is a free choice in which only one thing is actually offered. The term is often used to describe an illusion that multiple choices are available. The most well known Hobson's choice is “I'll give you a choice: take it or leave it”, wherein “leaving it” is strongly undesirable.
So Hobson’s choice is the exception to the ‘rule’ that a choice is deliberate — an example of “the exception proving the rule”, i.e. demonstrating that in normal circumstances choice is deliberate.
So deliberate is really redundant, unless one regards drawing straws as choosing.
I think there is some merit in the assertion by @user468772 that it can act as an intensifier, but most often I suspect that it is lazy habit.