We show that non-Markovian open quantum systems can exhibit exact Markovian dynamics up to an arbitrarily long time; the non-Markovianity of such systems is thus perfectly hidden, i.e. not experimentally detectable by looking at the reduced dynamics alone. This shows that non-Markovianity is physically undecidable and extremely counterintuitive, since its features can change at any time, without precursors. Some interesting examples are discussed.