Euler angles vs. Quaternions - problems caused by the tension between internal storage and presentation to the user?

Question

Quaternions are arguably an appropriate choice for representing object rotations internally. They are simple and efficient to interpolate and represent a single orientation unambiguously.

However, presenting quaternions in the user interface is generally inappropriate - Euler angles are generally much more familiar to users, and their values are a little more intuitive and predictable.

Euler angles suffer from being complicated at the code level - they require that an order of rotation is stored, and composing a practical orientation (be it matrix or quaternion) using this order and associated angles is cumbersome, to say the least.

Reliable interpolations are most conveniently performed using quaternion representation - so does this mean we must convert constantly between an Euler representation and a quaternion representation? Is this feasible in terms of performance?

Can we store the orientations as quaternions and convert them only for displayed to the user? This may not be possible because for any given orientation there is exactly one quaternion representation but many Euler representations. How do we 'pick' the Euler representation that corresponds to the one that originally defined that orientation? It seems like an impossible task - we've effectively lost information when converting to a quaternion.

Could we store as Euler angles and then convert to quaternions as needed? This probably isn't scalable - conversion from an Euler angle to a quaternion, interpolation, and then conversion back again is likely to be relatively expensive code.

Could we simply store both representations and use the most appropriate for any given situation? A large cost in terms of memory (imagine animation curves for a skeleton with around sixty bones) and keeping these values synchronised could be expensive, or at least cumbersome.

Has anybody seen, used or though up any clever solution to this problem? Surely the three options above aren't out only ones? Are there any other problem domains similar to this that have been solved?