Attentional orienting in complex visual environments is supported by statistical learning of regularities. For instance, visual search for a target is faster when a layout of nontargets is repeatedly encountered, illustrating that learned contextual invariances improve attentional guidance (contextual cueing; Chun & Jiang, 1998). Contextual learning is usually relatively efficient, but relocating the target (within an otherwise unchanged nontarget layout) typically abolishes contextual cueing, revealing only a slow recovery of learning (Zellin et al., 2014). While these studies usually employed artificial search displays with target and nontarget letters, the current study used more realistic natural scene contexts to determine whether a comparable lack-of-adaptation effect would also be evident in real-life contexts. Two experiments compared initial contextual cueing and the subsequent updating after a change in displays that either presented artificial letters, or natural scenes as contexts. With letter displays, an initial cueing effect was found that vanished after the change, thus replicating previous work. Natural scene displays showed a comparable reduction of cueing, which, however, depended on the size of initial learning: When the repeated scenes were explicitly recognized, contextual cueing revealed a large benefit, which attenuated costs associated with the change. By contrast, when scene-based cueing revealed non-explicit, incidental learning, the initial benefit turned into a cost - comparable to the pattern in letter displays. Together, these findings show that awareness about the repeating contexts is crucial to remedy costs after unexpected changes, while the “richness” of natural scene contexts themselves do not improve flexible contextual updating.