Don't connect the ULN directly to the µC, but insert a 74HC02's NOR gate into each line. Then, you need a reset controller with brown-out detection. Give the output of reset controller (e.g. MAX1232) not only to the reset pin of µC, but also to the other input of all 74HC02 NOR-gates.

So, whenever the µC is emitting logic high or whenever a brown-out condition is detected, the output of NOR gate is logic low, the input of ULN is logic low and the corresponding relay is off. Only when the port pin is logic low and the supply voltage is ok and the µC is running properly, the output of NOR gate is logic high and the corresponding relay turns on.

Kai Klaas