The end result was that rather than having people solve very simplistic problems that they could actually pull off in a 4x4-inch section of paper, students were to solve far more complex problems that actually test their understanding of what they are attempting to do instead of their grasp over carrying a 1.

Not in my experience.

Calculators were strictly forbidden at every math exam I've had at university. They tested my knowledge and understanding far better than any other exam I had. All I needed was to know the multiplication table (up to 12 helps), how to multiply larger numbers and how to divide numbers.

With calculators you may learn how to solve certain problems by rote, and thus score slightly higher on tests. That doesn't mean you have any understanding of the math involved. Tests where calculators are involved seem to be prone to this, at least in my experience (which is admittedly not that extensive). My girlfriend had "learned" math like this. She attempted to take further math classes, but quickly struggled as there was no longer a magic button that would rescue her.

I guess my point is that calculators doesn't do anything for understanding.

Doing trivial multiplication and addition on paper is a skill I believe most people should possess, and if you have that as a basis you can test their skills in everything from easy to complicated math problems.

They can of course help with productivity if you know what you're doing.