What country was this in? Quizzes and phone boxes sound.. odd. I've never heard of anything more complicated than rolling into your telco's nearest kiosk with your ID and them just provisioning a new one for you.
Lost phone was in Ukraine. We have both prepaid sim-cards and contract sim-cards. Contract would work like you've describes. Prepaid is more complicated.
