No sé que tipo de programa tienes en mente, pero una idea puede ser hacerte una máquina de estados, ya que te resultaría relativamente sencillo volver donde estabas. Tendrías que ir guardando también todas las variables que quieras reponer al inicio.
Ejemplo: Estado 1 => Led off y Estado 2=>Led On y la transición entre ellos es el estado de un pulsador. Tengo una variable llamada estado (byte) que indica en cual de los dos estados que estoy. Cada vez que cambio de estado, guardo en memoria no volátil dicha variable. Al inicio del programa, lo que haces es leer de memoria no volátil dicha variable, y ese será tu estado de inicio. El programa ejecuta las acciones que toque en cada estado, por lo que al iniciar irá al último estado guardado y seguirá su flujo normal.
Incluso podrías tener un camino diferente si se ha ido la corriente, y hacer ciertas cosas que te interesen (ejemplo arranque suave de motores, etc). Esto ya es dependiendo de lo que estes haciendo....
Bueno, explicado rápidamente y algo sencillo. Eso si, necesitas tener un mecánismo que ante un corte, te de tiempo de guardar todos tus registros de control en memoria.
http://arduino.cc/forum/index.php/topic,75826.0.html
Saludos
Igor R.