Correction, the relay I use is a G3VM-62C1. It costs $3.19, quite a bargin I think.

And yes, it always delays a restart after the power goes out, but only after the power goes out. As long as to power is on, the relay stays latched. The thermostat will not restart faster than 4 - 5 minutes on its own, but it has no provision for delay after a power loss.