I had the same isse.
Downloaded Estonia before going there to save roaming fees.
A big tile was missing below a certain zoom level. Made offline routing impossible in a big area, very annoying!
Later I connected to a wifi hotspot but I don't remember if I loged in to a Nokia Map page or tried routing once while online or not. After that the missing tile was available.
If it is not a bug, maybe it is an anti piracy feature where the device need to authenticate itself to activate random protected tiles?
I have no travel plans with my N9 in the near future so I can't verify this behaviour.