I think the real power of any tool we use is in its demonstration of the math our students think they know how to do, but do wrong. For example, as a seventh grade teacher, I introduce my 11 to 13-year-olds to the order of operations by giving them a problem in which they must divide before they multiply, as well as in which they will divide and multiply before they subtract, and with addition last. I ask them first to calculate the answer by hand, and then to calculate it on their calculator. Immediately, students remember PMDAS. However, they still do X before / and + before -. Of course, afterwards, most of the calcs come up with the right answer, and we then discuss the difference between what they were taught in previous years (the difference is not in what you were taught, but rather in the problems you were given--or not given--to solve) and the difference in calcs (some are "cheaper" and are not programmed with the correct order of operations. If you are using a calc that does not do the correct order of operations, then you must know the correct order of operations, or you will get the wrong answer, even when you use your calc).
In general, my handling of students and calcs is slightly different from your perspective of "I have always believed that children should be able to use calculators as they wish..." I allow my students to use their calculators (in fact, our school provides a tub of a dozen calculators for those who do not have one). However, there are times, when my purpose is to check up on a basic skill, when I will not allow the use. I also stress the difference between "showing process" which is required, and "doing scratch work" which does not need to be shown.
In addition, on the order of "...but that they certainly need to be discerning about their use. This they need to be taught," I find that calc use is very high at the beginning of the year, and then as we concentrate on calc short-cuts, and problem-solving, and a good problem-solver's time-line; and as they see me using the short-cuts to come up w/ answers before they do, using the calcs, they begin to realize that math is so much more than arithmetic, and the calcs begin to fall into a less prominent role.
I have not yet learned to use a graphing calculator (with which our 8th grade classes do a unit), or an "algebraic calculator" (of which I have heard, but with which I am not at all familiar). However, as we go through the year, we introduce things like using the memory to hold a constant for repetitive calculations, pressing the "equals key" over and over to find a power, and so on. I find this a most powerful tool for demonstrating why we must learn the "rules"...b/c the entire rest of the world knows them and uses them, and if we don't we will be the ones that are out of sync.
One final comment re: elementary textbooks. When my daughter was in 3rd grade, I ended up having a run-in w/ her teacher b/c she had used the correct order of operations on a problem on a quiz, but it was marked wrong and she lost credit. Knowing I was a math teacher, she had come to me to complain about the unfairness of being marked down for something she had done right. What I eventually found out is that most elementary math series, at that time, did what they called "chain problems" to help the student practice retaining one number in their heads while operating on it w/ another. We finally reached a compromise in which my daughter, at least, would never be given "chain problems" b/c I did not want her unlearning what she already knew correctly. I gave the teacher a step pattern to use for that skill, instead. I have, since that time, wondered if chain calculations are still in the elementary textbooks? At that time, I researched a half dozen elem math books, and found the concept, which was taught prior to the order of operations.
The problem, as I see it, is that such "pre-existing" pseudo-skills cause problems for those of us further up the chain, when we try to teach what was wrong about it. The kids come to us with some faulty knowledge, and we are stuck not just teaching, but unteaching first. I do hope that situation has changed by now.