I once specifically ran a game of France where my goal was to destory the colonizers (England, Portugal, and Castille) and did not pick Exploration myself, instead getting Influence first, which together with 'Justify My Wars' event (or whatever it's called), Exploration age ability for reduced AE, and Curia controlled just let me plow through Europe with rather low AE gains. I got bored around 1500s, but yeah, colonialism wouldn't have spawned til 1550ish or so (or whenever Ming/Netherlands/Norway found America). Might've gone way longer too.
As for randomly not triggering it without any intention behind the gameplay, well... one of my friends played a game where Portugal and Castille fell into unions under foreign powers (subjects do not pick Exploration) and France/England did not pick it early enough. I think it was like 1530ish or so and it had spawned, not sure how much longer it took before it finally appeared. I wish more institutions behaved like this without a set date to appear, and I also sort of wish the age of exploration lasted til 1520-1530 rather than 1505-1510 too.