After battery removal, time is set to 6:00 1.1.2009. When the phone connects to a GSM network, it does not immediately set the right time. I however suspect, that after some time (in tens of minutes or maybe even hours if my observations are correct), it eventually does.

I found that using GPS recorder will sync the time once it locks. Are there any other methods (less battery and time consuming) to force time sync (especially without internet access - I guess I could do something with ntpdate or similarin that case)? How does GSM synchronization work, is it expected to be delayed?

Sorry, dunno about without internet. There is openrdate which you might use in a cron job but I use sync-time-now-widget which adds a "Sync clock now" button to the system menu. I also make sure I only ever take the battery when I am within a WiFi zone. Although it could do it through a 2G or 3G internet connection if you don't mind risking a huge bill incurred by HAM trying to download a huge update at the same time.

If we knew the name of the executable/script which does it..

Thanks for the replies. Yeah, marmistrz, I wonder if there is a script that does GMS syncing.