My experience after a 5 day trip abroad (Rome); GPS lock on every time in 5 to 30 seconds. Every four times out of five in under 15 seconds, and most often instant approximated location by cellular positioning.

Powersaving off and no data connections allowed.
Pre-loaded maps and Nokia Maps in offline mode.
Normal cellular enabled, both 2g and 3g.

The cell tower based fast positioning seems to work well at least in some countries as without it the GPS lock on indeed would be that 10 to 20 minutes.