For a start AT*PSUTTZ=1 does nothing, look at the AT commands manual. You are already enabling this notification with AT+CLTS=1.
As to the missing *PSUTTZ: 2013, 7, 24, 3, 59, 13, "+40", 1 at startup, your provider is simply not sending the NITZ data when the modem connects to the local tower. What I have found is that a given provider wil ALWAYS either give the notification or not, whatever tower I happen to connect to. Are you saying that sometimes with the modem in the same location (and presumably connecting to the same tower) you sometimes do not see the *PSUTTZ: ... notification?
As to forcing time update, I don't think that you can do that.
Keep me updated as I am doing a very similar thing. We choose SIM cards very carefully to work reliably in different locations, and Vodafone simply never give the update at all (I am in Australia). Try asking the provider about NITZ and watch the blank look spread across their face.