I think another hallmark of an authentic problem is that it opens the possibility of surprise. When I'm writing a problem, either for my class or for a math contest, I usually have one or two particular approaches in mind--discussing those approaches is "the" point of doing the problem. But a characteristic of a really terrific problem is that solving it is not just a matter of finding your way through one specific set of doors in a maze: rather, it's more like navigating over rough terrain, where what seems like a detour might reveal itself to be a quicker, or more scenic, route. Students navigating such terrain for the first time surprise us with the new paths they discover.
One example of many: in the geometry text used at my school, CME Geometry, students learn early on about concurrence of perpendicular bisectors. Around that time, the text asks the following question: suppose you need to replace a broken blade from a circular saw. You have only the fragment shown below. How can you determine the blade's diameter?
In general, students find this problem quite difficult; in fact, in the first edition, it was a homework problem that almost nobody could solve.