After some tests I determined that I have to insert a 2.5ms break after powering up the chip before programming the first byte. Why should that be nescessary?

As long as I don't know more about your circuit, I can only guess: There can be some time 'constants' in your ciruit, needing this few milliseconds. Another guess: When using built-in oscillator in combination with quartz, mcu is allowed to need some milliseconds for stabilizing. May be that mcu needs this time for some other stuff, also? Sometimes in datasheet such a minimum time needed for being ready for programming after power-up is specified. I cannot remember where I saw this, but I did.
It's a only a feeling, but I would insert even a longer break for stabilizing: Something arround 10...20msec.

Bye,
Kai